L3 Informatique MPI4 – TD6 : Arithmétique modulaire

  1. Premiers pas.

    2. En Python, et donc aussi pour sympy, a mod n est donné par a % n. Affichez les tables de multiplication de ${\mathbb Z}/12{\mathbb Z}$ et de ${\mathbb Z}/13{\mathbb Z}$. Quels sont les éléments inversibles (et leurs inverses) dans les deux cas ?

  2. Algorithme d'Euclide étendu.


    3. a) Écrivez une fonction xgcd(a,b) qui renvoie un triplet $(d,u,v)$, où $d$ est le pgcd de $a,b$ et $d=ua+vb$ (coefficients de Bézout).
    b) Écrivez une fonction inversemod(a,n) qui calcule l'inverse de $a$ modulo $n$ s'il existe (et renvoie None sinon).

Par exemple, la table de multiplication modulo 7 est

 
 * 1 2 3 4 5 6
 1 1 2 3 4 5 6
 2 2 4 6 1 3 5
 3 3 6 2 5 1 4
 4 4 1 5 2 6 3
 5 5 3 1 6 4 2
 6 6 5 4 3 2 1
In [10]:
from TD6 import *
xgcd(1234,4321)
Out[10]:
(1, -1082, 309)
In [11]:
inversemod(1234,4321)
Out[11]:
3239
In [12]:
3239 * 1234 % 4321
Out[12]:
1

3. Petit théorème de Fermat

Affichez le triangle de Pascal jusqu'à $n=15$, successivement modulo 2,3,4,5. Où voyez-vous des zéros ?

On observe que lorsque $p$ est premier $$(a+b)^p \equiv a^p+b^p\ \mod p.$$

En itérant cette formule sur $a=1+1+\cdots +1$ ($a$ fois), on en déduit $$a^p\equiv a \mod p,$$ et si $a$ n'est pas divisible par $p$, il est inversible, d'où $$a^{p-1}\equiv 1 \mod p.$$

Quel est le chiffre des unités dans l'écriture de $3^{333333}$ en base 11 ?

4. Exponentiation modulaire

Écrivez une fonction powermod(a,m,n) qui calcule $a^m \mod n$ par l'algorithme d'exponentiation rapide et utilisez le pour tester des exemples du petit théorème de Fermat.

Voir le pseudo-code sur la page wikipedia, paragraphe "la méthode la plus efficace".

5. Le théorème de Wilson, et sa réciproque

Affichez les couples $(m, (m-1)! \mod m)$ pour m de 2 à 50. Que remarquez vous ?

Explorez les options de la fonction factor de sympy.

In [13]:
from sympy import *
var(' x ')
factor(x**6-1,modulus=7)
Out[13]:
(x - 3)*(x - 2)*(x - 1)*(x + 1)*(x + 2)*(x + 3)

Pouvez vous en déduire une preuve du théorème de Wilson : Si $p$ est premier, $(p-1)!+1\equiv 0 \mod p$

Que dire de la réciproque ?