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 ?

  3. Algorithme d'Euclide étendu.

  4. 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 [1]:
def tabmul(n):
    h = ' * ' + ''.join(["%3d"%i for i in range(1,n)])+'\n'
    for i in range(1,n):     
        l = ('%2d '% i ) + ''.join(["%3d"% ((i*j)%n) for j in range(1,n)])+'\n'
        h+=l
    return h

print tabmul(12) # 2,4,6,8,9,10 sont des diviseurs de 0
 *   1  2  3  4  5  6  7  8  9 10 11
 1   1  2  3  4  5  6  7  8  9 10 11
 2   2  4  6  8 10  0  2  4  6  8 10
 3   3  6  9  0  3  6  9  0  3  6  9
 4   4  8  0  4  8  0  4  8  0  4  8
 5   5 10  3  8  1  6 11  4  9  2  7
 6   6  0  6  0  6  0  6  0  6  0  6
 7   7  2  9  4 11  6  1  8  3 10  5
 8   8  4  0  8  4  0  8  4  0  8  4
 9   9  6  3  0  9  6  3  0  9  6  3
10  10  8  6  4  2  0 10  8  6  4  2
11  11 10  9  8  7  6  5  4  3  2  1


In [2]:
print tabmul(13) # ici, tout le monde est inversible
 *   1  2  3  4  5  6  7  8  9 10 11 12
 1   1  2  3  4  5  6  7  8  9 10 11 12
 2   2  4  6  8 10 12  1  3  5  7  9 11
 3   3  6  9 12  2  5  8 11  1  4  7 10
 4   4  8 12  3  7 11  2  6 10  1  5  9
 5   5 10  2  7 12  4  9  1  6 11  3  8
 6   6 12  5 11  4 10  3  9  2  8  1  7
 7   7  1  8  2  9  3 10  4 11  5 12  6
 8   8  3 11  6  1  9  4 12  7  2 10  5
 9   9  5  1 10  6  2 11  7  3 12  8  4
10  10  7  4  1 11  8  5  2 12  9  6  3
11  11  9  7  5  3  1 12 10  8  6  4  2
12  12 11 10  9  8  7  6  5  4  3  2  1


In [3]:
def xgcd(a, b):
    if a == 0 and b == 0: return (0, 0, 1)
    if a == 0: return (abs(b), 0, b/abs(b))
    if b == 0: return (abs(a), a/abs(a), 0)
    x_sign = 1; y_sign = 1
    if a < 0: a = -a; x_sign = -1
    if b < 0: b = -b; y_sign = -1
    x = 1; y = 0; r = 0; s = 1
    while b != 0:
        (c, q) = (a%b, a/b)
        (a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
    return (a, x*x_sign, y*y_sign)

xgcd(1234,4321)
Out[3]:
(1, -1082, 309)
In [4]:
def inversemod(a, n):
    g, x, y = xgcd(a, n)
    if g != 1:
        raise ZeroDivisionError, (a,n)
    assert g == 1, "a doit etre premier avec n."
    return x%n
inversemod(1234,4321)
Out[4]:
3239
In [5]:
3239 * 1234 % 4321
Out[5]:
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 ?

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 [6]:
def binomial(n,k):
    if n<k: return 0
    if k==0: return 1
    return binomial(n-1,k-1)+binomial(n-1,k)


def triangle(n,r):
    for m in range(n+1):
        print "%2d" % m,
        for k in range(m+1): 
            print "%3d" % (binomial(m,k) % r),
        print

triangle(15,2)
 0   1
 1   1   1
 2   1   0   1
 3   1   1   1   1
 4   1   0   0   0   1
 5   1   1   0   0   1   1
 6   1   0   1   0   1   0   1
 7   1   1   1   1   1   1   1   1
 8   1   0   0   0   0   0   0   0   1
 9   1   1   0   0   0   0   0   0   1   1
10   1   0   1   0   0   0   0   0   1   0   1
11   1   1   1   1   0   0   0   0   1   1   1   1
12   1   0   0   0   1   0   0   0   1   0   0   0   1
13   1   1   0   0   1   1   0   0   1   1   0   0   1   1
14   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1
15   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1

In [7]:
triangle(15,3)
 0   1
 1   1   1
 2   1   2   1
 3   1   0   0   1
 4   1   1   0   1   1
 5   1   2   1   1   2   1
 6   1   0   0   2   0   0   1
 7   1   1   0   2   2   0   1   1
 8   1   2   1   2   1   2   1   2   1
 9   1   0   0   0   0   0   0   0   0   1
10   1   1   0   0   0   0   0   0   0   1   1
11   1   2   1   0   0   0   0   0   0   1   2   1
12   1   0   0   1   0   0   0   0   0   1   0   0   1
13   1   1   0   1   1   0   0   0   0   1   1   0   1   1
14   1   2   1   1   2   1   0   0   0   1   2   1   1   2   1
15   1   0   0   2   0   0   1   0   0   1   0   0   2   0   0   1

In [8]:
triangle(15,4)
 0   1
 1   1   1
 2   1   2   1
 3   1   3   3   1
 4   1   0   2   0   1
 5   1   1   2   2   1   1
 6   1   2   3   0   3   2   1
 7   1   3   1   3   3   1   3   1
 8   1   0   0   0   2   0   0   0   1
 9   1   1   0   0   2   2   0   0   1   1
10   1   2   1   0   2   0   2   0   1   2   1
11   1   3   3   1   2   2   2   2   1   3   3   1
12   1   0   2   0   3   0   0   0   3   0   2   0   1
13   1   1   2   2   3   3   0   0   3   3   2   2   1   1
14   1   2   3   0   1   2   3   0   3   2   1   0   3   2   1
15   1   3   1   3   1   3   1   3   3   1   3   1   3   1   3   1

In [9]:
triangle(15,5)
 0   1
 1   1   1
 2   1   2   1
 3   1   3   3   1
 4   1   4   1   4   1
 5   1   0   0   0   0   1
 6   1   1   0   0   0   1   1
 7   1   2   1   0   0   1   2   1
 8   1   3   3   1   0   1   3   3   1
 9   1   4   1   4   1   1   4   1   4   1
10   1   0   0   0   0   2   0   0   0   0   1
11   1   1   0   0   0   2   2   0   0   0   1   1
12   1   2   1   0   0   2   4   2   0   0   1   2   1
13   1   3   3   1   0   2   1   1   2   0   1   3   3   1
14   1   4   1   4   1   2   3   2   3   2   1   4   1   4   1
15   1   0   0   0   0   3   0   0   0   0   3   0   0   0   0   1

In [10]:
triangle(15,7)
 0   1
 1   1   1
 2   1   2   1
 3   1   3   3   1
 4   1   4   6   4   1
 5   1   5   3   3   5   1
 6   1   6   1   6   1   6   1
 7   1   0   0   0   0   0   0   1
 8   1   1   0   0   0   0   0   1   1
 9   1   2   1   0   0   0   0   1   2   1
10   1   3   3   1   0   0   0   1   3   3   1
11   1   4   6   4   1   0   0   1   4   6   4   1
12   1   5   3   3   5   1   0   1   5   3   3   5   1
13   1   6   1   6   1   6   1   1   6   1   6   1   6   1
14   1   0   0   0   0   0   0   2   0   0   0   0   0   0   1
15   1   1   0   0   0   0   0   2   2   0   0   0   0   0   1   1

On voit clairement que pour $p$ premier, $(a+b)^p\equiv a^p+b^p \mod p$ (preuve donnée en cours), d'où le théorème en écrivant $(1+1+\cdots+1)^p$.

Comme 11 est premier, on a $3^{10}\equiv 1 \mod 11$. Donc $3^{333330+3}\equiv 3^3 = 27 \equiv 5 \mod 11$.

In [11]:
# pow(a,n,m) est a**n mod m 
pow(3,333333,11)
Out[11]:
5

Dire que dans ${\mathbb Z}/p{\mathbb Z}$, tout élément non nul vérifie $a^{p-1}-1=0$, c'est dire que les racines du polynôme $x^{p-1}-1$ sont exactement les $(p-1)$ éléments non nuls, ce que confirme la factorisation suivante :

In [12]:
from sympy import *
var(' x ')
factor(x**6-1,modulus=7)
Out[12]:
(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$

Oui : en posant $x=0$ dans $$\prod_{a=1}^{p-1}(x-a) \equiv x^{p-1}-1 \mod p$$ on voit que $$(-1)^{p-1}(p-1)! = \prod_{a=1}^{p-1}(-a) \equiv -1 \mod p$$ et comme $p-1$ est pair si $p>2$, on a bien $(p-1)!+1\equiv 0 \mod p$. Le cas particulier $p=2$ est trivial.

Que dire de la réciproque ?

Si le produit des éléments non nuls vaut $-1$, il n'y a pas de diviseurs de 0. Donc on est dans un corps, et $p$ est premier.

In [12]: