Congruences

[Emojigrin]

Bonjour,
voici un problème de congruence sur lequel je bloque j'espère que vous pourrez m'aider:
le \equiv correspond à "congru à"
la il faut s'imaginer un tableau, il est correcte)
n 0 1 2 3 4 5 6 7 8
3^n\equiv ...(7) 1 3 2 6 4 51 3 2

1) trouver le reste de la division de 3^3868 par 7
j'ai trouvé 4 qui est correcte

2) trouver le reste de la division de 6870^728 par 7 et la je bloque
je fais:
68703 \equiv 3 (7)
3 \equiv 3 (7)
728 \equiv 0 (7)
et après je pense qu'il faut mettre tout ça en lien mais je n'y parviens pas donc votre aide me serait d'un grand secours
merci d'avance

[aviateur]

Bonjour
Comme pour la première question tu as 728=128=8=2 mod (6)

Donc mod (7).

Maintenant 6870=-130=10=3 mod (7)

d'où 6870^728==9=2 mod (7)

[Emojigrin]

Pourquoi prendre un modulo (6) ?
merci de ta réponse

[aviateur]

Et bien j'ai pensé que c'est comme ça que tu avais fais la première question.

Tu as mod(7) c'est ce qui permet de tout calculer directo:


Donc



Sinon comment avais-tu fais?

[Emojigrin]

Je me rend compte que ma méthode pour le premier était du à a coup de chance j'ai l'impression...
Mais du coup je ne comprends pas pour quoi tu utilise le modulo (6) alors qu'on parle d'un modulo (7) ?

[Lostounet]

Salut,
Bon reprenons...
Moi non plus je vois pas pourquoi on parle de modulo 6?

Dans ce genre d'exercices le plus simple est d'essayer de trouver un certain entier n tel que 3^n = 1 [mod 7] ou bien un entier n tel que 3^n=(-1) [mod 7]

On constate par exemple pour la première question que:
3^3=27 = 6 [mod 7] = -1 [mod 7]

Mais 3868=3*1289 + 1

Donc (3^3)^1289 = (-1)^1289 [mod 7]
Alors 3^3867 = -1 [mod 7]

Puis en multiplant par 3:
3^3868=-3[mod 7] = 4 [mod 7]

Pour la deuxième question, 68703 = 7*9814 + 5
Ce qui veut dire que 68703= 5 [mod 7]

Et là pareil: tu cherches un certain entier n pour que 5^n = 1 [mod 7] ou bien 5^n =(-1) mod 7 comme tu veux.
Puis tu fais comme plus haut.

[Emojigrin]

Merci de ta réponse !
Mais pourquoi ne pas essayer avec 3^3 congru à 1 modulo 7 ?

[Emojigrin]

J'ai refait l'exà avec cette méthode elle me parle plus merci beaucoup à vous deux en tout cas

[Lostounet]

Merci de ta réponse !
Mais pourquoi ne pas essayer avec 3^3 congru à 1 modulo 7 ?

Euh... Car 3^3=27 n'est pas congru à 1 modulo 7... Mais à -1.

Tu voulais dire 3^6 ? (lui est congru à 1 mod 7 comme te le dit Aviateur). Tu peux aussi... Tu trouveras pareil. Tu vois comment on sait qui est congru à quoi modulo 7 ? :p Pose la question si c'est flou y'a aucune honte à avoir des doutes (c'est dur les congruences).

Le tout est de trouver quelqu'un pour que ça fasse 1 ou (-1) comme ça on peut élever à une puissance énorme facilement.

Un résultat d'algèbre avancé nous suggère 5^2 ou 5^3 ou 5^6 à tester (en fait 5 exposant d avec d un diviseur de 6) mais bon ça c'est pas indispensable à savoir :p

[Emojigrin]

Oui je voulais dire 6 oups j'ai compris merci bcq