Terminale Option Experte / Annales sur la congruence 10 exercices (100% corrigés)

a
1. Exercices non-classés E.3142 Rappel: Pour deux entiers relatifs a et b , on dit que a est congru à b modulo 7 , et on écrit a ≡ b ( mod. 7) lorsqu’il existe un entier relatif k tel que a = b +7 k . 1 Cette question constitue une restitution organisée de con-naissances : a Soient a , b , c et d des entiers relatifs. Démontrer que : Si a ≡ b ( mod. 7) et c ≡ d ( mod. 7) alors a · c ≡ b · d ( mod. 7) . b En déduire que : pour a et b entiers relatifs non nuls. Si a ≡ b ( mod. 7) alors pour tout entier naturel n : a n ≡ b n ( mod. 7) . 2 Pour a =2 puis pour a =3 , déterminer un entier naturel n non nul tel que : a n ≡ 1 ( mod. 7) . 3 Soit a un entier naturel non divisible par 7 . a Montrer que : a 6 ≡ 1 ( mod. 7) . b On appelle ordre de a ( mod. 7) , et on désigne par k , le plus petit entier naturel non nul tel que a k ≡ 1 ( mod. 7) . Montrer que le reste r de la division euclidienne de 6 par k vérifie a r ≡ 1 ( mod. 7) . En déduire que k divise 6. Quelles sont les valeurs possibles de k ? c Donner l’ordre modulo 7 de tous les entiers a compris entre 2 et 6. 4 À tout entier naturel n , on associe le nombre : A n = 2 n + 3 n + 4 n + 5 n + 6 n . Montrer que : A 2006 ≡ 6 ( mod. 7) E.3187 Étant donné un entier naturel n 2 , on se propose d’étudier l’existence de trois entiers na-turels x , y et z tels que : x 2 + y 2 + z 2 ≡ 2 n − 1 ( mod. 2 n ) Partie A : Étude de deux cas particuliers : 1 Dans cette question, on suppose que n =2 . Montrer que 1 , 3 et 5 satisfont à la question précédente. 2 Dans cette question, on suppose n =3 . a Soit m un entier naturel. Reproduire et compléter le tableau ci-dessous donnant le reste r de la division eu-clidienne de m par 8 et le reste R de la division eucli-dienne de m 2 par 8. r 0 1 2 3 4 5 6 7 R b Peut-on trouver trois entiers naturels x , y et z tels que : x 2 + y 2 + z 2 ≡ 7 ( mod. 8) ? Partie B: Étude du cas général où n 3 : Supposons qu’il existe trois entiers naturels x , y et z tels que : x 2 + y 2 + z 2 ≡ 2 n − 1 ( mod. 2 n ) 1 Justifier le fait que les trois entiers naturels x , y et z sont tous impairs ou que deux d’entre eux sont pairs. 2 On suppose que x et y sont pairs et que z est impair. On pose alors: x = 2 q ; y = 2 r ; z = 2 s + 1 où q , r , s sont des entiers naturels. a Montrer que : x 2 + y 2 + z 2 ≡ 1 ( mod. 4) . b En déduire une contradiction. 3 On suppose que x , y , z sont impairs. a Prouver que, pour tout entier naturel k non nul, k 2 + k est divisible par 2 . b En déduire que : x 2 + y 2 + z 2 ≡ 3 ( mod. 8) . c Conclure. https://chingmath.fr chapExoCorrec/3142 sacados/3142 chapExoCorrec/3187 sacados/3187
E.3240 Partie A Soit N un entier naturel, impair non premier. On suppose que N = a 2 − b 2 où a et b sont deux entiers na-turels. 1 Montrer que a et b n’ont pas la même parité. 2 Montrer que N peut s’écrire comme produit de deux en-tiers naturels p et q . 3 Quelle est la parité de p et de q ? Partie B On admet que 250 507 n’est pas premier. On se propose de chercher des couples d’entiers naturels ( a ; b ) vérifiant la relation: ( E ) : a 2 − 250 507 = b 2 1 Soit X un entier naturel. a Donner dans un tableau, les restes possibles de X mod-ulo 9 ; puis ceux de X 2 modulo 9 . b Sachant que a 2 − 250 507= b 2 , déterminer les restes pos-sibles modulo 9 de a 2 − 250 507 ; en déduire les restes possibles modulo 9 de a 2 . c Montrer que les restes possibles modulo 9 de a sont 1 et 8 . 2 Justifier que si le couple ( a ; b ) vérifie la relation ( E ) , alors a 501 . Montrer qu’il n’existe pas de solution du type (501 ; b ) . 3 On suppose que le couple ( a ; b ) vérifie la relation ( E ) . a Démontrer que a est congru à 503 ou à 505 modulo 9 . b Déterminer le plus petit entier naturel k tel que le cou-ple (505+9 k ; b ) soit solution de ( E ) , puis donner le couple solution correspondant. Partie C 1 Déduire des parties précédentes une écriture de 250 507 en un produit deux facteurs. 2 Les deux facteurs sont-ils premiers entre eux? 3 Cette écriture est-elle unique? E.3319 1 a Déterminer suivant les valeurs de l’entier naturel non nul n le reste dans la division euclidienne par 9 de 7 n . b Démontrer alors que : 2005 2005 ≡ 7 ( mod. 9) . 2 a Démontrer que pour tout entier naturel non nul n : 10 n ≡ 1 ( mod. 9) . b On désigne par N un entier naturel écrit en base dix, on appelle S la somme de ses chiffres. Démontrer la relation suivante : N ≡ S ( mod. 9) . c En déduire que N est divisible par 9 si, et seulement si, S est divisible par 9 . 3 On suppose que A = 2005 2005 ; on désigne par : B la somme des chiffres de A ; C la somme des chiffres de B ; D la somme des chiffres de C . a Démontrer la relation suivante : A ≡ D ( mod. 9) . b Sachant que 2005 < 10000 , démontrer que A s’écrit en numération décimale avec au plus 8020 chiffres. En déduire que : B 72180 . c Démontrer que : C 45 . d En étudiant la liste des entiers inférieurs à 45, déter-miner un majorant de D plus petit que 15. e Démontrer que : D =7 . E.3554 Dans tout l’exercice, n désigne un entier naturel non nul. 1 a Pour 1 n 6 , calculer les restes de la division eucli-dienne de 3 n par 7 . b Démontrer que, pour tout n , 3 n +6 − 3 n est divisible par 7 . En déduire que 3 n et 3 n +6 ont le même reste dans la division par 7. c À l’aide des résultats précédents, calculer le reste de la division euclidienne de 3 1 000 par 7 . d De manière générale, comment peut-on calculer le reste de la division euclidienne de 3 n par 7 , pour n quel-conque? e En déduire que, pour tout entier naturel n , 3 n est pre-mier avec 7 . 2 Soit U n =1+3+3 2 + ··· +3 n − 1 = n − 1 i =0 3 i , où n est un entier naturel supérieur ou égal à 2. a Montrer que si U n est divisible par 7 alors 3 n − 1 est divisible par 7. b Réciproquement, montrer que si 3 n − 1 est divisible par 7 alors U n est divisible par 7 . En déduire les valeurs de n telles que U n soit divisibles par 7 . https://chingmath.fr chapExoCorrec/3240 sacados/3240 chapExoCorrec/3319 sacados/3319 Antilles-Guyane Juin 2005 5 points chapExoCorrec/3554 sacados/3554
E.3570 1 Démontrer que, pour tout entier naturel n , 2 3 n − 1 est un multiple de 7 (on pourra utiliser un raisonnement par récurrence) . En déduire 2 3 n +1 − 2 est un multiple de 7 et que 2 3 n +2 − 4 est un multiple de 7 . 2 Déterminer les restes de la division par 7 des puissances de 2. 3 Le nombre p étant un entier naturel, on considère le nom-bre entier: A p = 2 p + 2 2 p + 2 3 p a Si p =3 n , quel est le reste de la division de A p par 7? b Démontrer que si p =3 n +1 alors A p est divisible par 7. c Étudier le cas où p =3 n +2 . E.3572 On se propose de déterminer les couples ( n ; m ) d’entiers naturels non nuls vérifiant la relation: 7 n − 3 × 2 m = 1 ( F ) 1 On suppose m 4 . Montrer qu’il y a exactement deux couples solutions. 2 On suppose maintenant que m 5 . a Montrer que si le couple ( n ; m ) vérifie la relation ( F ) alors: 7 n ≡ 1 ( mod. 32) . b En étudiant les restes de la division par 32 des puis-sances de 7, montrer que si le couple ( n ; m ) vérifie la relation ( F ) alors n est divisible par 4 . c En déduire que si le couple ( n ; m ) vérifie la relation ( F ) alors: 7 n ≡ 1 ( mod. 5) d Pour m 5 , existe-t-il des couples ( n ; m ) d’entiers na-turels vérifiant la relation ( F ) ? 3 Conclure, c’est-à-dire déterminer l’ensemble des couples d’entiers naturels non nuls vérifiant la relation ( F ) . E.3629 On appelle ( E ) l’ensemble des entiers naturels qui peuvent s’écrire sous la forme 9+ a 2 où a est un entier naturel non nul ; par exemple: 10 = 9 + 1 2 ; 13 = 9 + 2 2 ; . . . On se propose dans cet exercice d’étudier l’existence d’éléments de ( E ) qui sont des puissances de 2 , 3 ou 5 . 1 Étude de l’équation d’inconnue a : a 2 + 9 = 2 n où a ∈ N , n ∈ N , n 4 . a Montrer que si a existe, a est impair. b En raisonnant modulo 4 , montrer que l’équation pro-posée n’a pas de solution. 2 Étude de l’équation d’inconnue a : a 2 + 9 = 3 n où a ∈ N , n ∈ N , n 3 . a Montrer que si n 3 , 3 n est congru à 1 ou à 3 modulo 4 . b Montrer que si a existe, il est pair et en déduire que nécessairement n est pair. c On pose n =2 p où p est un entier naturel, p 2 . Dé-duire d’une factorisation de 3 n − a 2 , que l’équation pro-posée n’a pas de solution. 3 Étude de l’équation d’inconnue a : a 2 + 9 = 5 n où a ∈ N , n ∈ N , n 2 . a En raisonnant modulo 3 , montrer que l’équation n’a pas de solution si n est impair. b On pose n =2 p , en s’inspirant de 2 c démontrer qu’il existe un unique entier naturel a tel que a 2 +9 soit une puissance entière de 5 . https://chingmath.fr chapExoCorrec/3570 sacados/3570 chapExoCorrec/3572 sacados/3572 chapExoCorrec/3629 sacados/3629 Asie Juin 2004
E.5863 Partie A On considère la fonction f issue d’un algorithme où ses argu-ments prennent pour valeurs des entiers naturels non-nul : Fonction f(a;b) c ← 0 Tant que a>b c ← c+1 a ← a − b Fin Tant que Renvoyer (c;a) 1 Indiquer les valeurs des variables prises successivement lors de l’appel à la fonction f avec les valeurs a =13 et b =4 . 2 Comment interpréter, en fonction des valeurs a et b fournies en argument, la valeur du couple renvoyé par la fonction f lors d’un appel. Partie B À chaque lettre de l’alphabet, on associe, grâce au tableau ci-dessous, un nombre entier compris entre 0 et 25 . a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25 On définit un procédé de codage de la façon suivante : Étape 1: A la lettre que l’on veut coder, on associe le nom-bre entier m correspond dans le tableau. Étape 2: On calcule le reste de la division euclidienne de 9 m +5 par 26 et on le note p . Étape 3: Au nombre entier p , on associe la lettre corre-spondante dans le tableau. 1 Coder la lettre U . 2 Modifier la fonction f de l’algorithme de la partie A pour qu’à une valeur de m entrée par l’utilisateur, il renvoie la valeur de p , calculée à l’aide du procédé de codage précédent. Partie C 1 Trouver un nombre entier x tel que : 9 x ≡ 1 ( mod. 26) . 2 Démontrer alors l’équivalence : 9 m +5 ≡ p ( mod. 26) ⇐⇒ m ≡ 3 p − 15 ( mod. 26) 3 Décoder alors la lettre B . E.5960 1 Démontrer que, pour tout entier naturel n , 2 3 n − 1 est un multiple de 7 (on pourra utiliser un raisonnement par récurrence) . En déduire que 2 3 n +1 − 2 est un multiple de 7 et que 2 3 n +2 − 4 est un multiple de 7 . 2 Déterminer les restes de la division par 7 des puissances de 2 . 3 Le nombre p étant un entier naturel, on considère le nom-bre entier: Q p = 2 p + 2 2 p + 2 3 p a Si p =3 n , quel est le reste de la division de A p par 7 ? b Démontrer que si p =3 n +1 alors A p est divisible par 7 . c Étudier le cas où p =3 n +2 4 On considère les nombres entiers a et b écrits dans le sys-tème binaire : a = 1 001 001 000 ; b = 1 000 100 010 000 Vérifier que ces deux nombres sont des nombres de la forme A p . Sont-ils divisibles par 7 ? E.6795 Les parties A et B peuvent être traitées de manière indépendante. Partie A Afin de crypter un message, on utilise un chiffrement affine. Chaque lettre de l’alphabet est associée à un nombre entier comme indiqué dans le tableau ci-dessous : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Soit x le nombre entier associé à la lettre à coder. On déter-mine le reste y de la division euclidienne de 7 x +5 par 26 , puis on en déduit la lettre associée à y (c’est elle qui code la lettre d’origine) . Exemple : M correspondant à x =12 7 × 12 + 5 = 89 Or 89 ≡ 11 ( mod. 26) et 11 correspondant à la lettre L , donc la lettre M est codée par la lettre L . 1 Coder la lettre L . 2 a Soit k un entier relatif. Montrer que si k ≡ 7 x ( mod. 26) alors 15 · k ≡ x ( mod. 26) . b Démontrer la réciproque de l’implication précédente. c En déduire que y ≡ 7 x +5 ( mod. 26) équivaut à x ≡ 15 · y +3 ( mod. 26) . 3 À l’aide de la question précédente décoder la lettre E . Partie B On considère les suites a n et b n telles que a 0 et b 0 sont des entiers compris entre 0 et 25 inclus et pour tout entier naturel n : a n +1 = 7 · a n + 5 b n +1 = 15 · b n + 3 Montrer que pour tout entier naturel n : a n = a 0 + 5 6 × 7 n − 5 6 https://chingmath.fr chapExoCorrec/5863 sacados/5863 chapExoCorrec/5960 sacados/5960 Polynesie Juin 1999 chapExoCorrec/6795 sacados/6795
On admet pour la suite du problème que pour tout entier na-turel n : b n = b 0 + 3 14 × 15 n − 3 14 Partie C Déchiffrer un message codé avec un chiffrement affine ne pose pas de difficulté (on peut tester les 312 couples de coefficients possibles) . Afin d’augmenter cette difficulté de décryptage, on propose d’utiliser une clé qui indiquera pour chaque lettre le nombre de fois où on lui applique le chiffrement affine de la partie A . Par exemple pour coder le mot MATH avec la clé 2 − 2 − 5 − 6 , on applique ˇ2ı fois le chiffrement affine à la lettre M (cela donne E ) , ˇ2ı fois le chiffrement de la lettre A , ˇ5ı fois le chiffrement à la lettre T et enfin ˇ6ı fois le chiffrement à la lettre H . Dans cette partie, on utilisera la clé 2 − 2 − 5 − 6 . Décoder la lettre Q dans le mot IY Y Q . https://chingmath.fr