Bonjour !
Je bloque sur un exercice qui mêle congruences et suites :/
1. a. Pour n compris entre 0 et 6 calculer les reste de la division euclidienne de 3^n par 7
==> Je l'ai fait et j'ai les résultats
b. A l'aide des résultats précédents, calculer le reste de la division euclidienne de 3^1000 par 7 ?
==> Je n'arrive pas à le faire je tourne en rond en faisant la division euclidienne de 1000 par 7...
c. De manière générale, comment peut-on calculer le reste de la division euclidienne de 3^n par 7 pour n quelconque ?
==> J'en ai absolument aucune idée
d. En déduire que pour tout entier naturel n, 3^n n'est pas divisible par 7
==> Je n'y arrive pas non plus...
Voilà, merci si vous avez quelques idées
John
Congruences et suites
-
John (Terminale S)
-
SoS-Math(11)
- Messages : 2881
- Enregistré le : lun. 9 mars 2009 18:20
Re: Congruences et suites
Bonsoir John,
1000 est congru à 4 modulo 6 donc \(3^{1000}\) à le même reste que \(3^n\). Tu dois faire la division par 6 pas par 7.
Pour \(3^n\), tu recherches le reste de n par 6 et tu en déduis les restes en fonction de la congruence de n modulo 6.
Tu peux en conclure pour le c)
Y a t'il un reste égal à 0 ? Conclus.
Bonne continuation.
1000 est congru à 4 modulo 6 donc \(3^{1000}\) à le même reste que \(3^n\). Tu dois faire la division par 6 pas par 7.
Pour \(3^n\), tu recherches le reste de n par 6 et tu en déduis les restes en fonction de la congruence de n modulo 6.
Tu peux en conclure pour le c)
Y a t'il un reste égal à 0 ? Conclus.
Bonne continuation.
-
John (Terminale S)
Re: Congruences et suites
Bonsoir,
Désolé mais je ne comprends pas cette ligne
"1000 est congru à 4 modulo 6 donc 3^{1000} à le même reste que 3^n"
Désolé mais je ne comprends pas cette ligne
"1000 est congru à 4 modulo 6 donc 3^{1000} à le même reste que 3^n"
-
Antoine
Re: Congruences et suites
Bonsoir,
Je ne comprends vraiment pas...
Si je pars de 1000 = 6 * 166 + 4
Son reste dans la division euclidienne vaut bien 4 (si on divise par 6)
Donc 1000 congru à 4 (6)
Comment vous arrivez à dire que 3^1000 est congru à 3^n (6) ?
Je ne comprends vraiment pas...
Si je pars de 1000 = 6 * 166 + 4
Son reste dans la division euclidienne vaut bien 4 (si on divise par 6)
Donc 1000 congru à 4 (6)
Comment vous arrivez à dire que 3^1000 est congru à 3^n (6) ?
-
SoS-Math(11)
- Messages : 2881
- Enregistré le : lun. 9 mars 2009 18:20
Re: Congruences et suites
Re bonsoir,
En effet, j'en étais déjà à la question suivante c'est \(3^{1000}\) et \(3^4\) qui ont le même reste dans la division par 7 ; désolé.
Sinon cequi est important est de comprendre que c'est modulo 6 qu'il faut travailler puisque \(3^6\) et \(3^0\) ont le même reste donc les restes reviennent de manière cyclique.
Bon courage
En effet, j'en étais déjà à la question suivante c'est \(3^{1000}\) et \(3^4\) qui ont le même reste dans la division par 7 ; désolé.
Sinon cequi est important est de comprendre que c'est modulo 6 qu'il faut travailler puisque \(3^6\) et \(3^0\) ont le même reste donc les restes reviennent de manière cyclique.
Bon courage
-
John (Terminale S)
Re: Congruences et suites
Bonjour,
J'ai essayé de faire quelque chose et je voudrais bien votre avis ^^
Car pour ma part je pense avoir réussis mais avec une congruence modulo 7.
On sait que 3^6 congru 1 (7)
Or 1 = 3^0 comme vous l'avez dit (merci d'ailleurs ça m'a bien aidé)
Donc 3^6 congru 3^0 (7)
En mettant à la puissance k, on aurait 3^6k congru 3^0k (7) donc 3^6k congru 3^0 (7)
On sait que tout entier naturel n peut s'écrire sous la forme n = 6k + r où k est un entier naturel
Si on multiplie par 3^r, 3^6k * 3^r congru 3^0 * 3^r (7)
Ainsi 3^(6k + r) congru 3^(0 + r) (7)
Donc 3^n congru 3^r (7)
Ainsi pour n = 1000, comme 1000 = 166 * 6 + 4, alors on peut dire que 3^1000 congru 3^4 (7) ?
Et comme 3^4 congru 4 (7)
Alors 3^1000 congru 4 (7)
De plus, la question d'après, on me demande comment je peux calculer de manière générale le reste de la division euclidienne de 3^n par 7 pour n quelconque
J'ai mis ceci comme justification :
On sait que pour tout n de la forme n = 6k + r, on a bien 3^n congru 3^r (7)
Pour calculer le reste de la division euclidienne de 3^n par 7, il suffit de trouver le reste r de n dans la division euclidienne par 7 puis d'appliquer les congruences.
Exemple : 3^723 congru ? (7)
723 = 120*6 + 3
Donc 3^723 congru à 3^3 (7)
Comme 3^3 congru à 6 (7)
Alors 3^723 congru à 6 (7)
Voilà, est-ce que selon vous c'est possible de rédiger de cette manière ? ^^
Par contre je n'arrive pas à démontrer le d :/
J'ai essayé de faire quelque chose et je voudrais bien votre avis ^^
Car pour ma part je pense avoir réussis mais avec une congruence modulo 7.
On sait que 3^6 congru 1 (7)
Or 1 = 3^0 comme vous l'avez dit (merci d'ailleurs ça m'a bien aidé)
Donc 3^6 congru 3^0 (7)
En mettant à la puissance k, on aurait 3^6k congru 3^0k (7) donc 3^6k congru 3^0 (7)
On sait que tout entier naturel n peut s'écrire sous la forme n = 6k + r où k est un entier naturel
Si on multiplie par 3^r, 3^6k * 3^r congru 3^0 * 3^r (7)
Ainsi 3^(6k + r) congru 3^(0 + r) (7)
Donc 3^n congru 3^r (7)
Ainsi pour n = 1000, comme 1000 = 166 * 6 + 4, alors on peut dire que 3^1000 congru 3^4 (7) ?
Et comme 3^4 congru 4 (7)
Alors 3^1000 congru 4 (7)
De plus, la question d'après, on me demande comment je peux calculer de manière générale le reste de la division euclidienne de 3^n par 7 pour n quelconque
J'ai mis ceci comme justification :
On sait que pour tout n de la forme n = 6k + r, on a bien 3^n congru 3^r (7)
Pour calculer le reste de la division euclidienne de 3^n par 7, il suffit de trouver le reste r de n dans la division euclidienne par 7 puis d'appliquer les congruences.
Exemple : 3^723 congru ? (7)
723 = 120*6 + 3
Donc 3^723 congru à 3^3 (7)
Comme 3^3 congru à 6 (7)
Alors 3^723 congru à 6 (7)
Voilà, est-ce que selon vous c'est possible de rédiger de cette manière ? ^^
Par contre je n'arrive pas à démontrer le d :/
-
SoS-Math(9)
- Messages : 6351
- Enregistré le : mer. 5 sept. 2007 12:10
Re: Congruences et suites
Bonjour Johnny,
Ce que tu as fait semble juste.
Pour la question d, existe-t-il un reste égal à 0 ... non car tous les restes sont congrus à ^1, 2 , ..,6 d'après la questi0ns précédentes !
donc aucun nombre de la forme 3^n n'est divisible par 7.
SoSMath.
Ce que tu as fait semble juste.
Pour la question d, existe-t-il un reste égal à 0 ... non car tous les restes sont congrus à ^1, 2 , ..,6 d'après la questi0ns précédentes !
donc aucun nombre de la forme 3^n n'est divisible par 7.
SoSMath.
-
John (Terminale S)
Re: Congruences et suites
Bonjour,
Oui je suis d'accord mais comment je peux rédiger cette question car j'ai l'idée en tête mais je ne sais pas comment la rédiger...
Aussi, dans le 2 est dit
"Soit Un = 1 + 3 + 3² + ... 3^(n-1)" où n entier supérieur ou égal à 2"
a. Montrer que si Un est divisible par 7 alors 3^n - 1 aussi
==> Ça okay
b. Réciproquement, montrer que si 3^n - 1 est divisible par 7, alors 2Un est divisible par 7, puis à l'aide d'un tableau de congruences, que Un est alors divisible par 7.
==> J'ai réussi jusqu'à 2Un divisible par 7 mais je ne comprends pas l'idée ici de faire un tableau de congruences ?
Est-ce que vous pourriez me dire comment je dois m'y prendre ? Genre je dois d'abord mettre Un congru à 0 1 2 3 4 5 6 puis je fais 2Un congru à 0 2... ?
c. En déduire les valeurs de n telles que Un est divisible par 7
==> On sait que Un congru à 0 (7)
Donc que 3^n - 1 congru à 0 (7)
Donc 3^n congru à 1 (7)
On avait vu que 3^6 congru 1 (7)
Ainsi il faut que les n soient de la forme n = 6k où k est un entier (car 3^6k est aussi congru à 1^k où 1 (7))
Voilà merci de votre aide ^^
John
Oui je suis d'accord mais comment je peux rédiger cette question car j'ai l'idée en tête mais je ne sais pas comment la rédiger...
Aussi, dans le 2 est dit
"Soit Un = 1 + 3 + 3² + ... 3^(n-1)" où n entier supérieur ou égal à 2"
a. Montrer que si Un est divisible par 7 alors 3^n - 1 aussi
==> Ça okay
b. Réciproquement, montrer que si 3^n - 1 est divisible par 7, alors 2Un est divisible par 7, puis à l'aide d'un tableau de congruences, que Un est alors divisible par 7.
==> J'ai réussi jusqu'à 2Un divisible par 7 mais je ne comprends pas l'idée ici de faire un tableau de congruences ?
Est-ce que vous pourriez me dire comment je dois m'y prendre ? Genre je dois d'abord mettre Un congru à 0 1 2 3 4 5 6 puis je fais 2Un congru à 0 2... ?
c. En déduire les valeurs de n telles que Un est divisible par 7
==> On sait que Un congru à 0 (7)
Donc que 3^n - 1 congru à 0 (7)
Donc 3^n congru à 1 (7)
On avait vu que 3^6 congru 1 (7)
Ainsi il faut que les n soient de la forme n = 6k où k est un entier (car 3^6k est aussi congru à 1^k où 1 (7))
Voilà merci de votre aide ^^
John
-
SoS-Math(9)
- Messages : 6351
- Enregistré le : mer. 5 sept. 2007 12:10
Re: Congruences et suites
John,
Supposons que Un ne soit pas divisible par 7. Donc on a un des cas suivants :
Un congru à 1 modulo 7 donc 2Un congru à 2 modulo 7
Un congru à 2 modulo 7 donc 2Un congru à 4 modulo 7
Un congru à 3 modulo 7 donc 2Un congru à 6 modulo 7
...
Un congru à 6 modulo 7 donc 2Un congru à 5 modulo 7
Dans tous les cas 2Un n'est congru à 0 modulo 7, donc 2Un n'est pas divisble par 7 ce qui faux par hypothèse
Donc par l'absurde Un est divisible par 7.
SoSMath.
Supposons que Un ne soit pas divisible par 7. Donc on a un des cas suivants :
Un congru à 1 modulo 7 donc 2Un congru à 2 modulo 7
Un congru à 2 modulo 7 donc 2Un congru à 4 modulo 7
Un congru à 3 modulo 7 donc 2Un congru à 6 modulo 7
...
Un congru à 6 modulo 7 donc 2Un congru à 5 modulo 7
Dans tous les cas 2Un n'est congru à 0 modulo 7, donc 2Un n'est pas divisble par 7 ce qui faux par hypothèse
Donc par l'absurde Un est divisible par 7.
SoSMath.
-
John (Terminale S)
Re: Congruences et suites
Bonjour,
Je ne comprends pas trop votre explication mais elle ne fait pas intervenir un tableau de congruence comme mon énoncé me le demande non ?
Du coup il faut bien que je fasse un tableau de congruences non ?
Je ne comprends pas trop votre explication mais elle ne fait pas intervenir un tableau de congruence comme mon énoncé me le demande non ?
Du coup il faut bien que je fasse un tableau de congruences non ?
-
SoS-Math(9)
- Messages : 6351
- Enregistré le : mer. 5 sept. 2007 12:10
Re: Congruences et suites
John,
Avec ce que je t'ai donné tu peux faire un tableau ... et conclure ?
SoSMath.
Avec ce que je t'ai donné tu peux faire un tableau ... et conclure ?
SoSMath.
-
John (Terminale S)
Re: Congruences et suites
Bonjour,
Justement c'est le tableau que je ne vois pas comment faire !
Est-ce que je dois d'abord faire un tableau avec Un puis une seconde ligne avec 2Un
Par exemple,
Un 0 1 2 3 4 5 6
2Un 0 1 4 6 8 10 12
Sachant que le seul cas possible est lorsque Un congru à 0 (7) ?
Justement c'est le tableau que je ne vois pas comment faire !
Est-ce que je dois d'abord faire un tableau avec Un puis une seconde ligne avec 2Un
Par exemple,
Un 0 1 2 3 4 5 6
2Un 0 1 4 6 8 10 12
Sachant que le seul cas possible est lorsque Un congru à 0 (7) ?
-
John (Terminale S)
Re: Congruences et suites
Rebonjour (et désolé du double post),
Je voulais savoir si j'ai bien compris.
Votre raisonnement par l'absurde consiste à montrer que si l'on considère Un non divisible par 7, alors pour tout cas on obtient 2Un non divisible par 7.
Et que donc par l'absurde, si Un est divisible par 7, alors 2Un est divisible par 7 ?
De plus, vous ne faîtes pas figurer Un congru à 0 car il ne rentre pas dans le cas où Un est non divisible par 7 ?
Merci pour vos réponses !
Je voulais savoir si j'ai bien compris.
Votre raisonnement par l'absurde consiste à montrer que si l'on considère Un non divisible par 7, alors pour tout cas on obtient 2Un non divisible par 7.
Et que donc par l'absurde, si Un est divisible par 7, alors 2Un est divisible par 7 ?
De plus, vous ne faîtes pas figurer Un congru à 0 car il ne rentre pas dans le cas où Un est non divisible par 7 ?
Merci pour vos réponses !
-
SoS-Math(9)
- Messages : 6351
- Enregistré le : mer. 5 sept. 2007 12:10
Re: Congruences et suites
John,
Oui ton tableau est juste ! (sauf pour 1 ...)
Ensuite il faut simplifier ... tu écris 2Un congru à 8 modulo 7 soit 1 modulo 7.
SoSMath.
Oui ton tableau est juste ! (sauf pour 1 ...)
Ensuite il faut simplifier ... tu écris 2Un congru à 8 modulo 7 soit 1 modulo 7.
SoSMath.
-
John (Terminale S)
Re: Congruences et suites
Bonjour,
Oui en effet pardon pour 1, j'ai oublié de mettre 2 au lieu de 1.
Donc, si j'ai bien compris, je peux :
1. Faire mon tableau de congruences comme ceci
2. Faire le raisonnement par l'absurde que vous m'avez conseillé ?
Oui en effet pardon pour 1, j'ai oublié de mettre 2 au lieu de 1.
Donc, si j'ai bien compris, je peux :
1. Faire mon tableau de congruences comme ceci
2. Faire le raisonnement par l'absurde que vous m'avez conseillé ?