Déterminer le reste d'une division euclidienne et congruence

Bonjour à tous, et merci d'avance à ceux qui m'aideront pour ce DM, je tiens à préciser que je n'ai pas tout à fait compris cette notion de congruence, elle me paraît un peu complexe
Voilà l’exercice :

Conjecturer le reste obtenu dans la division euclidienne de 17^n par 13 en prenant les valeurs de n, et prouver la conjecture grâce aux congruences. En déduire le reste de 17^2016 puis 17^2017 dans la division euclidienne par 13.
Conjecturer les congruences modulo 11 de 10^n (= les restes dans la division euclidienne par 11 de 10^n ) et prouver cette conjecture

En remarquant que 707 487 = 7 x 10^5 + 7 x 10^3 + 4 x 10^2 + 8 x 10 + 7 prouver que (707 487) ^2015 est un multiple de 11.

Bonsoir Breezy94,

Indique tes éléments de réponse et la question qui te pose problème.
Question 1)
Quels sont les restes possibles ?

17 = 1 x 13 + 4..

17 ≡ 4 [13]

Il n'y a pas un seul reste :
si n = 2
si n = 3,
.....

Si n = 2 :
$17^2$ ≡ 4^2 [13]
On a : 17^2 ≡ 3 [13]
17^2≡ -10 [13]
Ce qui donne 17^2 ≡ -10 [13]
Si n = 3 :
17^3 ≡ 4 ^3 [13]
≡ 64 [13]
≡ 12 [13]
≡-1 [13]

Pourquoi des restes négatifs ?

si n = 1, 17 ≡ 4 [13]
si n = 2, 17² ≡ 3 [13]
si n = 3, 17³ ≡ 12 [13]
si n = 4, $17^4$ ≡ 9 [13]
....

Tu continues jusqu'a trouver un reste identique à celui de n = 1

si n = 1, 17 ≡ 4 [13]
si n = 2, 17² ≡ 3 [13]
si n = 3, 17³ ≡ 12 [13]
si n = 4, 17^4 ≡ 9 [13]
si n = 5, $17^5$ ≡ 10 [13]
pour n=6 6 , $17^6$ ≡ 14 [13]
pour n=7 $17^7$ ≡ 4 [13]

Une erreur pour n = 6

si n = 1, 17 ≡ 4 [13]
si n = 2, 17² ≡ 3 [13]
si n = 3, 17³ ≡ 12 [13]
si n = 4, $17^4$ ≡ 9 [13]
si n = 5, $17^5$ ≡ 10 [13]
pour n=6, $17^6$ ≡ 1 [13]
pour n=7 $17^7$ ≡ 4 [13]

Donc si n = 1+6k, $17^n$ ≡ 4 [13]
si n = 2+6k, ...
....

Pourquoi n= 1+6k ? ..
si n = 2+6k, $17_n$ ≡ 3 [13]
si n = 3+ 6k $17^n$ ≡ 12 [13]
...
si n = 7 +6k , $17^n$ ≡ 4[13]

Pour n = 1 et n = 7, on trouve le même reste 4 et 7 = 1+ 6
soit n = 1 + 6k

Ah d'accord et comment en déduire le reste de 17^2016..

Il faut chercher comment s'écrit 2016
1 + 6k ?
2 + 6k ?

soit
2016 = 6k + ....

6k + 2016 ?

Non

2016 = 335x6 + 6 ou 336 x 6
donc correspond à n = 6 et le reste est .....

1 ?

Oui.

et pour 2017 ?

2017 = 335x6+7 le reste est 4 ?

2017 = 336x6 + 1 donc le reste est 4.

Tu appliques le même raisonnement pour la question 2.

On écrit donc $17^{2017}$ ≡ 4 [13] ?

Oui

La questions 2 est plus complexe je trouve car c'est le diviseur qui a la puissance n .. pour n = 1 : 11 ≡ 1 $10^1$ ]
pour n = 1, 2,3 ect 11 ≡ 11 [10 $^n$ ]

Ah non je me suis embrouillé excusez moi, je le fais là

Donc pour n = 1
$10^1$ ≡ 10 [11]
n=2
$10^2$ ≡ 1 [11]
n=3
$10^3$ ≡ 10 [11]

C'est correct.

"En remarquant que 707 487 = 7 x 10^5 + 7 x 10^3 + 4 x 10^2 + 8 x 10 + 7 prouver que (707 487) ^2015 est un multiple de 11."
je n'y arrive pas

......

Si la puissance de 10 est impaire, tu remplaces par 10 et si elle est paire tu remplaces par 1
donc 707487 est congru à 7 x 10 + .......
et tu vérifies que le nombre trouvé est un multiple de 11

707487 est congru à 7 x 10 + 10 ?

Non
7 x 10 + 7 x 10 +4 +8x10 +7 = 22 X10 + 11
= 11 [ ...... ]
donc
....

Je n'y comprends rien

A partir de :

$10^1$ ≡ 10 [11]
n=2
$10^2$ ≡ 1 [11]
n=3
$10^3$ ≡ 10 [11]
tu dois déduire et démontrer que
si n est pair le reste est 1 et si n est impair le reste est 10,
C'est ce que tu appliques à 707487.

Donc 707 487 ≡ 10 [11] ?

Non C'est congrue à 0;

J'ai indiqué le résultat à compléter dans un précédent post.

Pouvez- vous répondre concrètement à la question 2 ? j'essayerai de comprendre après la correction, cela fait plus d'une semaine que je suis sur le même exercice et je n'y arrive vraiment pas :frowning2:

A partir de :

101 ≡ 10 [11]
n=2
102 ≡ 1 [11]
n=3
103 ≡ 10 [11]
tu dois déduire et démontrer que
si n est pair le reste est 1 et si n est impair le reste est 10,
C'est ce que tu appliques à 707487.
7 x 10^5 + 7 x 10^3 + 4 x 10^2 + 8 x 10 + 7 congru à
7 x 10 + 7 x 10 + 4 x 1 + 8 x 10 + 7 soit
7 x 10^5 + 7 x 10^3 + 4 x 10^2 + 8 x 10 + 7
22 x 10 + 11 =
11(2x10+ 1) donc un multiple de 11
donc 707 487 est un multiple de 11

Si tu ne factorises pas, tu peux écrire
22 x10 + 11 = 231 = 21 x 11 donc multiple de 11

Et pour (707 487)^2015 ..

Si 707 487 est un multiple de 11, il s'écrit sous la forme 11 x k et
707487^2015 = 11^2015 x k^2015 donc c'est un multiple de 11

D'accord, et une dernière question.. Pour prouver la conjecture du 2) nous ne devons pas faire comme la question 1) ?..

Oui,

Tu appliques le même raisonnement