Re: 143

Le 05/12/2024 07:51, robby a écrit :

Le 04/12/2024 à 22:54, Olivier Miakinen a écrit :

Leur produit étant de la forme (6n+1)(6n−1) = 36n² − 1, ils sont congrus à
−1 modulo 2, modulo 3, modulo 4, modulo 6, modulo 9, modulo 12, modulo 18 et
modulo 36 !

 
uh, tu veux développer comment on en arrive a la contrainte de congruence ?
j'ai tj eu des problèmes à cette étape ! :-)

Pas de problème. Je commence par définir ce que l'on appelle congruence, ce pour
répondre aussi à Dominique.


Pour simplifier commençons par ne traiter que les entiers positifs. Deux entiers
positifs a et b sont congrus modulo N (un autre entier positif) si et seulement
si le reste de la division de a par N et le reste de la division de b par N sont
égaux.

Par exemple, les nombres 307, 427, 30027 et 99997 sont tous congrus modulo 10
puisque le reste de leur division par 10 donne 7. Ils sont congrus *entre eux*
modulo 10, mais bien sûr ils sont aussi congrus à 7 modulo 10, puisque le reste
de la division de 7 par 10 est également 7.

S'agissant des entiers négatifs, la notion de division entière ne marche plus
vraiment, et pourtant les nombres −3, −5003 et −9993 sont aussi congrus à 7
modulo 10. On peut alors utiliser une autre définition, qui fonctionne pour
tous les entiers positifs et négatifs. Deux entiers relatifs a et b sont congrus
modulo un entier positif N, si et seulement si N divise (a − b).

Prenons quelques exemples.
 a = 427, b = 307 : a − b = 120 = 12 × 10
 a = −3, b = 307 : a − b = −310 = (−31) × 10
 a = −3, b = −5003 : a − b = 5000 = 500 × 10


Maintenant je vais expliquer pourquoi les nombres de la forme 36n² − 1 sont
congrus à −1 modulo n'importe quel nombre N dans { 2, 3, 4, 6, 9, 12, 18, 36 }.

Tous les nombres de cette liste sont des diviseurs de 36. Par exemple, si je
choisis N = 9, on a N × 4 = 36. Alors, pour montrer que 36n² − 1 est congru
à −1 modulo 9, prenons a = 36n² − 1, b = −1, et N = 9. Il vient :
 a − b = (36n² − 1) − (−1) = 36n² − 1 + 1 = 36n² = 4×9 n² = 4n² × 9 = (4n²) × N
On a bien : a − b est un multiple de N, donc a est congru à b modulo N.

 
( et raisonnement en espace quotientés en général.
par ex toujours pour mes polynomes de permutation, je butte sur
comprendre et implémenter ça:
https://en.wikipedia.org/wiki/Permutation_polynomial#Quadratic_permutation_polynomials_(QPP)_over_finite_rings
)

Alors là c'est moi qui coince. Et pour commencer je ne suis pas sûr de voir le
rapport avec les congruences modulo N.


--
Olivier Miakinen