Congruences

[upium666]

Bonjour à tous et à toutes !

Soit un entier naturel
Soit un entier relatif tel que :
A quoi est congru modulo ?

Je pense qu'il y a une équation diophantienne à résoudre, enfin ché pas trop comment faire :p

Merci de m'aider

[L.A.]

Bonsoir.

Vu que n et n-1 sont premiers entre eux, un entier A congru à 1 modulo n peut être congru à n'importe quoi modulo n-1. Il n'y a pas de lien entre les deux.

Prenons n=7 : 8,15,22,29,... sont congrus à 1 mod 7 mais à 2,3,4,5,... mod 6

[jlb]

1 + (A-1)/n ??

[zygomatique]

salut

il existe des entiers relatifs u et v tels que ua + vn = 1 ua + v(n - 1) = 1 - v

d'autre part on sait que une fois trouvé un couple (u, v) solution alors les solutions sont les couples (U, V)= (u - kn,, V + ka)

donc Ua + V(n - 1) = 1 - V

il suffit de trouver les valeurs de k tels que

....

[jlb]

salut

il existe des entiers relatifs u et v tels que ua + vn = 1 ua + v(n - 1) = 1 - v

d'autre part on sait que une fois trouvé un couple (u, v) solution alors les solutions sont les couples (U, V)= (u - kn,, V + ka)

donc Ua + V(n - 1) = 1 - V

il suffit de trouver les valeurs de k tels que

....

euh, c'est pas plutôt: il existe x tel que A-1=xn d'où A-1-x=x(n-1) donc x=(A-1)/n et A est congru à 1+x modulo n-1

[L.A.]

1 + (A-1)/n ??

Certes, mais cette formule suppose qu'on connaisse l'entier A alors que (si mon interprétation de la question est correcte) on sait seulement que sa classe modulo n est 1.
Et si on connait l'entier A, on connait automatiquement sa classe modulo n'importe quoi.

Mais je me trompe peut-être effectivement de problème...

[zygomatique]

a - 1 = xn <==> a - xn = 1 <==> a(1 + kn) + (-x -ka)n = 1

k variant dans Z

....

[zygomatique]

certes oui mais on peut donner la forme de ce "n'importe quoi" ....

[paquito]

Je pense qu'il n'y a pas de réponse; par exemple on a 10^k=1[9] pour tout entier k, mais, modulo 8,
10^0=1, 10=2, 10^2=4, 10^3=0 et après 10^k=0, ce qui fait 4 possibilités qui ne découlent pas de 10^k=1[9]. Je suis complètement d'accord avec L.A.

[L.A.]

Bon OK, comme A est congru a 1 mod n, on en déduit que A est congru à 1+(A-1)/n mod n-1.
Mais en quoi est-ce que cette formule est plus utile que A congru à A mod (n-1) ?

Pour les A petits, ta formule donne LE reste situé entre 0 et n-2 disons, mais pour les A plus grands il faudra écrire d'autres formules, et encore d'autres plus A est grand, etc...

[chan79]

1 + (A-1)/n ??

J'aurais dit ça aussi.
On sait qu'il existe un entier k tel que A=1+k*n (on a k=(A-1)/n)

A=1+k(n-1)+k
A=1+k modulo (n-1)
A=1+(A-1)/n modulo (n-1)
Reste à savoir à quoi ça pourrait servir ???

10000=1 modulo 9 donne
10000=1+1111=1112 modulo 8 :look2:

[paquito]

A=1[n] signifie qu'il existe un entier q supposé>=1 tel que A=nq+1, donc on a aussi A=(n-1)q+q+1, soit A=q+1[n-1] ce qui ne se déduit pas du tout de A=1[n]; il faudrait faire la division euclidienne de (A-1) par n pour répondre et obtenir un résultat inexploitable si q est grand : strictement aucun intérêt; autant faire la division euclidienne de A par n-1.

[jlb]

J'aurais dit ça aussi.
On sait qu'il existe un entier k tel que A=1+k*n (on a k=(A-1)/n)

A=1+k(n-1)+k
A=1+k modulo (n-1)
A=1+(A-1)/n modulo (n-1)
Reste à savoir à quoi ça pourrait servir ???

10000=1 modulo 9 donne
10000=1+1111=1112 modulo 8 :look2:

Salut Chan, à rien à priori: la personne qui a posté aime bien les maths et se pose des questions, des énigmes à un niveau TS je crois. Je pense que c'est ce qu'il attendait. Après, je me trompe peut-être. Et dans tous les cas, je pense qu'il apprécie qu'on lui réponde, comme toute personne sur ce site.