Un peu d'arithmetique - Page 1

Ce message et ce qu'il contient sont distribués sous GPL.

Qlq'un peut me dire s'il y'a qlque chose de faux ou d'optimisable la dedans svp ?

J'ai vu en cours l'algo d'Euclide pour calculer les pgcd (entre des polynomes mais bon "il y'a une analogie avec ce qui se passe ds N" comme dirait mon prof).
Seulement on a rien vu pour calculer le ppcm. Alors voila (la preuve est de moi => peut-être brouillon et sans doute boiteuse) :

Soient A,B € N*
Soient u,a,b € N* u = pgcd(A,B), A = a*u , B = b*u
A*B = a*b*u² => A*B/pgcd(A,B) = a*b*u
(1) A|a*b*u
(2) B|a*b*u
Soit k € N* A|k et B|k :
A|k => a|k et u|k }
} => a|k, b|k, u|k => (3) a*b*u|k
B|k => b|k et u|k }

(1),(2),(3) => a*b*u = ppcm(A,B)

Donc A*B/pgcd(A,B) = ppcm(A,B)

Procedure de calcul du pgcd en asm 8086 (désolé je parle ce que je connais le mieux (le moins mal en fait). Je pense que le "portage" n'est pas bien compliqué)
;In ax=A bx=B (A>B svp)
;Out ax=pgcd(A,B)
;sauvegarde eventuelle de registres...
pgcd
xor dx,dx
div bx
mov ax,bx
mov bx,dx
cmp dx,0
jne pgcd
;restauration des registres...
ret

Avec ça, l'écriture de la routine ppcm est franchement triviale.

Merci à ceux qui prendront la peine de se pencher la dessus et encore plus à ceux qui auront des remarques constructives et/ou pertinentes.

attend, tu veux quoi exactement ?

ya plus qu'une analogie, c'est exactement la même chose dans tous les anneaux euclidiens (Z, polynomes...)

A part ça on a

A*B/pgcd(A,B) = ppcm(A,B) A PEU PRES car il faut normaliser le polynome obtenu!! (le coeff dominant du Ppcm est 1)

"Qlq'un peut me dire s'il y'a qlque chose de faux ou d'optimisable la dedans svp ? "
ça veut dire dans les grandes lignes :
Est ce que ma demonstration se tient ?
Est ce qu'on peut faire une routine de pgcd mieux (plus rapide ou plus courte) ?

ta démo est fausse

telchar>> Je vais peut être avoir l'air ignard là mais "normaliser le polynome" euh c'est à dire ? Sinon je pensais juste appliquer ce truc à des entiers (c'est pour ça que A,B € N*)

par exemple un pgcd ou un ppcm ne peut pas etre 2x^3-4x+1

mais x^3-2x+1/2

(le coeff dominant est 1)

telchar>>pkoi ?

paske c'est comme ça bigrediou!!

pour avoir l'unicité du pgcd et du ppcm on doit fixer le coeff dominant et comme on est pas con on prend 1.

telchar>> okay... et pour les nombres est ce que ça pose le même problème ?

le problème équivalent avec les entiers, c'est que le pgcd/ppcm doit etre POSITIF

là oui je suis bien d'accord mais avec mon truc on peut trouver un ppcm ou un pgcd négatif ?

ra ben zut excuse moi j'ai pas vu le N*... effectivement comme ça ça marche, je croyais A et B seulement entiers

telchar>> bon si tu daignes relire ma demonstration, tu verras qu'aucun poly n'y est mentionné ; aussi te serais-je gré de bien vouloir m'expliquer plus precisement pkoi elle n'et pas vraie sur N*. Sinon donne moi un algo de calcul du ppcm sur N* stp

j'étais en train de taper ma reponse j'avais pas vu la tienne désolé il faut bien lire les ennoncé camarade merci quand même et @+

mais tu veux quoi exactement ?

Mathieu : je ne peux pas t'aider, moi et les maths...

Tiens j'ai rien à faire alors je te donne ma routine de calcul du pgcd en asm z80, mais je pense pas que ça te serve dans la vie

;; In hl=A de=B
;; Out de=pgcd(A,B)

pgcd:
push hl
or a
sbc hl,de
pop hl
jr nc,$+3
ex de,hl
or a
sbc hl,de
jr nz,pgcd
ret

hum hum...
Soient A,B € N* >>> ok
Soient u,a,b € N* u = pgcd(A,B), A = a*u , B = b*u >>>ok
A*B = a*b*u² => A*B/pgcd(A,B) = a*b*u >>> ok
(1) A|a*b*u >>> ok d'apres hypothese
(2) B|a*b*u >>> d'apres hypothese
Soit k € N* A|k et B|k : >>> admettons...

A|k => a|k et u|k }
} => a|k, b|k, u|k => (3) a*b*u|k
B|k => b|k et u|k }

FAUX!

Bon d'apres mes petits souvenir de spe maths:
THEOREME DE GAUSS:
A*B|C ^ PGCD(A,C)=1 => B|C
or ce que tu applique c'est quoi au juste, car si tu applique gauss, c'est completement faut ton truc...
donc ta demo est fausse a partir d'ici...

un peut de logique ne fait pas de mal
A|k => a|k v u|k (1)
B|k => b|k v u|k (2)
(1) ^ (2) => a|k v b|k v u|k

=> ((a*b*u|k ^ pgcd(u,k)=1) => a*b|k ) v ( (pgcd(u,k)!=1 ^ pgcd(a,u)!=1 ^ pgcd(b,u)!=1 )=> a*b*u|k) v ( (pgcd(a,k)=1 ^ pgcd(b,k)=1) => a*b*u | k)

etc... Je viens de te demontrer que ta demo est fausse..
il advient que toute la suite est fausse

Mais le théorème qu'il cite est juste sur |N* (même si la démonstration est fausse)!

TiMad>>Euh j'avais un peu zappé Gauss en effet. On demontre ça comment alors ?
Miles>>Je veux savoir comment on demontre ça tu comprends maintenant ?

ah OK... je croyais que tu voulais un algo ou autre cgose - t'aurais dû aller sur le forum scolaire... -

c'est pas a|b*c et pgcd(a,c)=1=>a|b ?

TiMad, je ne suis pas sûr de ce que tu as écrit...

je connais pas l'asm z80 mais bon.

jr nz,pgcd
ret

c'est sauter à une routine puis faire un return, si je ne m'abuse? un simple branchement serait plus simple et plus rapide

miles>>heureux qu'on se comprennent enfin Mais s'il y'a qlq'un des algos de calcul de ppcm/pgcd, je suis prenneurr
yheam>>Merci bien

pour le pgcd, tu prends Euclide :
en boucle jusqu'à ce que b soit nul :
a-b->a
si a<b, échanger a et b
recommencer

à la place de a-b, tu peux aussi mettre a%b

tu t'es de nouveau trompé!!

A*B| pi(xn,1,n) <=> (A|pi(xn,1,n) v B|pi(xn,1,n))

c'est faux!!

et soit logique, si pgcd(A,C)=1, on ne peut avoir A*B|C, sauf si A=1...