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
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
print tabmul(13) # ici, tout le monde est inversible
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)
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)
3239 * 1234 % 4321
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 ?
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.
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)
triangle(15,3)
triangle(15,4)
triangle(15,5)
triangle(15,7)
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$.
# pow(a,n,m) est a**n mod m
pow(3,333333,11)
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 :
from sympy import *
var(' x ')
factor(x**6-1,modulus=7)
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>3$, 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.