Arithmetique

[Babe]

Bonjour,

je cherche une peu d'aide, merci d'avance

1) comment faut il resoudre une equation du type bezout
442u+495v=1
(il y a surement un algorithme ?)


2)petite question: si PGCD(a,b)=1, a et b premier entre eux ?
comment montre t-on qu'un nombre est premier ?



merci d'avance

[serge75]

ça s'appelle l'algorithme d'euclide :
495=442+53, et donc 53=495-442
442=8*53+18, et donc 18=442-8*(495-442)=9*442-8*495
53=2*18+17, et donc 17=(495-442)-2*(9*442-8*495)=17*495-19*442
18=17+1 donc 1=(9*442-8*495)-(17*495-19*442)=28*442-25*495

sinon, oui, pgcd(a,b)=1 signifie exactement que a et b sont premiers entre eux.
Pour montrer qu'un nombre est premier, le plus simple (s'il n'est pas trop grand) est de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée.
Exemple : 101
il n'est divisible ni par 2, ni par 3, ni par 5, ni par 7 et 11²>101, donc 101 est premier.
Tu peux aussi regarder du côté du crible d'érathostène (ortho incertaine), qui permet d'avoir tous les nombres premiers entre 1 et n, assez rapidement pour peu que n ne soit pas trop grand.