Flashcard: Cours sur la Théorie des Nombres — 18 carte

Divisibilité — définition ?

b|a signifie qu'il existe q tel que a=bq.

Multiple d’un entier — définition ?

Un entier a est multiple de b si a=bq pour un q.

Division euclidienne — formule ?

a=bq+r avec 0≤r<|b|.

Quotient — rôle ?

Entier q dans a=bq+r.

Reste euclidien — rôle ?

Entier r tel que 0≤r<|b|.

Congruence modulo n — définition ?

a≡b (mod n) si n|(a−b).

Reste modulo n — propriété ?

Unique r dans {0,...,n−1} tel que a≡r (mod n).

Petit théorème de Fermat — formule ?

Si p premier et p∤a, alors a^{p−1}≡1 (mod p).

Corollaire Fermat — formule ?

a^p≡a (mod p) pour p premier.

PGCD — définition ?

Plus grand diviseur commun de a et b.

Algorithme d’Euclide — étape clé ?

pgcd(a,b)=pgcd(b,r) dans a=bq+r.

Nombres premiers — caractéristique ?

Nombre avec exactement deux diviseurs entiers distincts.

Nombres premiers — infini ?

Oui, il y en a une infinité.

Premiers entre eux — définition ?

pgcd(a,b)=1.

ppcm — définition ?

Plus petit commun multiple de a et b.

Inverse modulo b — condition ?

Existe si pgcd(a,b)=1.

Identité de Bézout — formule ?

a∧b=1 si et seulement s’il existe u,v tels que au+bv=1.

Équation diophantienne — forme ?

ax+by=c avec a,b,c entiers et x,y inconnues entières.