JEUX & PROBLÈMES
GroLopin
Figure 1.
\ = ()
Intersections des droites
à coefficients dans {O, 1}
s
modulo 2 à gauche,
avec les points à l'infini
à droite. À noter que
sur le graphique à gauche,
les droites en croix sont
parallèles : modulo 2, les
droites y = 1 + x et y = 1- x
sont identiques ;
à droite, la droite y = x est
représentée par un cercle.
C r=O
On a ainsi construit une c ie nts dans {O; 1}.
représentation du plus Elles o nt pour équati ons y = ax + b po ur
petit plan projectif a et b dans {O; 1} e t x = c po ur c dans
(intituléplandeFano). { 0; l } .
Considé ro ns Je reste de la di visio n euclidie nne par 2 (on dit la vale ur « modulo
2 ») de chaque o pérati o n arithmétique :
a ins i, 1 + 1 sera équivale nt à O et do nc
la droite y = x + 1 passera (cf. fi g ure 1)
par le po int ( ] ; 0).
La fi gure 2 dévo ile un jeu de pin 's max imal po ur N = 3.
On ajoute le po int à l' infini 00 3 à to utes
les droites pa rallè les de pe nte a ; a ins i,
to utes les droites de pe nte O (y = 0 et
y = 1) se coupe ront e n un nou veau po int
nommé 00 0 , to utes les droites de pe nte
1 (y = xet y = x + l )se couperont e n oo 1
e t toutes les droites de pe nte infini e
(x = 0 et x = l ) se coupe ront en 00 00 •
La résolution pour n - 1 premier
Pl açon s-nous mainte nant où N - 1 = p
est un nombre pre mier.
On appe lle NP = {O ; 1 ; ... ;p - 1} l'ensemble des e ntie rs modulo p (tous les
calcul s y seront e ffectués e n ide ntifiant
a e t a+ p ).
On considè re le cadre géné ral de droites
D a;b: y= ax + b et de verticales
V c : x = c où a , b et c appartienne nt à
NP. Les points d ' inte rsection sont les p
2
points du pl an{ (x ; y), x, y E NP} au xB
X
que ls il fa ut ajouter les p + 1 points à l' infini {ooa, a E NP} U { 00 00 } .
Dé no mbrons- les :
• c hac une des p
2 d roites D 0 :b passe par
les p po ints (x; ax + b) po ur x E N,,}
a in s i qu e le p o int à l ' in f ini oo";
soit p + 1 = N po ints en to ut ;
• c hac un e des p ve rti ca les V c passe
pa r les p po ints (c ; y) po ur y E N,,
a ins i que le po int à l' infini 00 00 so it
p + 1 = N po ints en tout ;
• l a d ro it e infini e p asse p a r les
p + 1 = N po ints à l' infini .
Ana lysons les inte rsecti o ns :
• les verticales Ve se coupe nt e n 00 00 pa r
définiti o n ;
• pour a fixé EN,,, les droites D a:b se coupe nt e n oo a par définiti o n ;
• chaque droite (sauf la d roite infinie)
passe par un unique po int à l' in fi ni ,
d o nc co upe la d ro ite infini e e n un
unique point ;
• to ute droite D a:b coupe to ute droite Y c
e n le point (c; ac + b)
• si a "# a', D a:b coupe D a.:b' e n un poi nt
(x; y) vé rifi ant y= ax + b = a'x + b '
soit (a - a ' )x = b ' - b ma is comme p est
pre mie r, le thé orè me de Bézout no us
affirme l'ex iste nce d 'entie rs re latifs u
et v te ls que u(a -a') + vp = 1 e t do nc :
u(a - a')x = u(b ' - b) = x (mod p ) est
l ' unique solution de l'équati o n . Do nc
les dro ites se coupent en un unique point.
130 Tangente Hors-série n°52. Mathématiques & informatique
GroLopin
Figure 1.
\ = ()
Intersections des droites
à coefficients dans {O, 1}
s
modulo 2 à gauche,
avec les points à l'infini
à droite. À noter que
sur le graphique à gauche,
les droites en croix sont
parallèles : modulo 2, les
droites y = 1 + x et y = 1- x
sont identiques ;
à droite, la droite y = x est
représentée par un cercle.
C r=O
On a ainsi construit une c ie nts dans {O; 1}.
représentation du plus Elles o nt pour équati ons y = ax + b po ur
petit plan projectif a et b dans {O; 1} e t x = c po ur c dans
(intituléplandeFano). { 0; l } .
Considé ro ns Je reste de la di visio n euclidie nne par 2 (on dit la vale ur « modulo
2 ») de chaque o pérati o n arithmétique :
a ins i, 1 + 1 sera équivale nt à O et do nc
la droite y = x + 1 passera (cf. fi g ure 1)
par le po int ( ] ; 0).
La fi gure 2 dévo ile un jeu de pin 's max imal po ur N = 3.
On ajoute le po int à l' infini 00 3 à to utes
les droites pa rallè les de pe nte a ; a ins i,
to utes les droites de pe nte O (y = 0 et
y = 1) se coupe ront e n un nou veau po int
nommé 00 0 , to utes les droites de pe nte
1 (y = xet y = x + l )se couperont e n oo 1
e t toutes les droites de pe nte infini e
(x = 0 et x = l ) se coupe ront en 00 00 •
La résolution pour n - 1 premier
Pl açon s-nous mainte nant où N - 1 = p
est un nombre pre mier.
On appe lle NP = {O ; 1 ; ... ;p - 1} l'ensemble des e ntie rs modulo p (tous les
calcul s y seront e ffectués e n ide ntifiant
a e t a+ p ).
On considè re le cadre géné ral de droites
D a;b: y= ax + b et de verticales
V c : x = c où a , b et c appartienne nt à
NP. Les points d ' inte rsection sont les p
2
points du pl an{ (x ; y), x, y E NP} au xB
X
que ls il fa ut ajouter les p + 1 points à l' infini {ooa, a E NP} U { 00 00 } .
Dé no mbrons- les :
• c hac une des p
2 d roites D 0 :b passe par
les p po ints (x; ax + b) po ur x E N,,}
a in s i qu e le p o int à l ' in f ini oo";
soit p + 1 = N po ints en to ut ;
• c hac un e des p ve rti ca les V c passe
pa r les p po ints (c ; y) po ur y E N,,
a ins i que le po int à l' infini 00 00 so it
p + 1 = N po ints en tout ;
• l a d ro it e infini e p asse p a r les
p + 1 = N po ints à l' infini .
Ana lysons les inte rsecti o ns :
• les verticales Ve se coupe nt e n 00 00 pa r
définiti o n ;
• pour a fixé EN,,, les droites D a:b se coupe nt e n oo a par définiti o n ;
• chaque droite (sauf la d roite infinie)
passe par un unique po int à l' in fi ni ,
d o nc co upe la d ro ite infini e e n un
unique point ;
• to ute droite D a:b coupe to ute droite Y c
e n le point (c; ac + b)
• si a "# a', D a:b coupe D a.:b' e n un poi nt
(x; y) vé rifi ant y= ax + b = a'x + b '
soit (a - a ' )x = b ' - b ma is comme p est
pre mie r, le thé orè me de Bézout no us
affirme l'ex iste nce d 'entie rs re latifs u
et v te ls que u(a -a') + vp = 1 e t do nc :
u(a - a')x = u(b ' - b) = x (mod p ) est
l ' unique solution de l'équati o n . Do nc
les dro ites se coupent en un unique point.
130 Tangente Hors-série n°52. Mathématiques & informatique