Terminale Option Experte / Annales sur le PGCD 35 exercices (dont 32 corrigés)

a
1. PGCD, propriété et congruence E.5284 1 a Montrer que 3 n 3 − 11 n +48 est divisible par n +3 pour tout entier naturel n . b Montrer que 3 n 2 − 9 n +16 est un entier naturel non nul pour tout entier naturel n . 2 Montrer que, pour tous les entiers naturels non nuls a , b et c , l’égalité suivante est vraie: pgcd ( a ; b ) = pgcd ( b · c − a ; b ) 3 Montrer que, pour tout entier naturel n , supérieur ou égal à 2 , l’égalité est vraie: pgcd (3 n 3 − 11 n ; n +3)= pgcd (48 ; n +3) 4 a Déterminer l’ensemble des diviseurs entiers naturels de 48 . b En déduire l’ensemble des entiers naturels n tels que 3 n 3 − 11 n n +3 soit un entier naturel. E.5285 Les suites d’entiers naturels x n et y n sont définies par : x 0 = 3 ; x n +1 = 2 · x n − 1 y 0 = 1 ; y n +1 = 2 · y n + 3 1 Démontrer par récurrence que pour tout entier n ∈ N : x n = 2 n +1 + 1 2 a Calculer le PGCD de x 8 et x 9 , puis celui de x 2002 et x 2003 . Que peut-on en déduire pour x 8 et x 9 d’une part, pour x 2002 et x 2003 d’autre part? b x n et x n +1 sont-ils premiers entre eux pour tout entier naturel n ? 3 a Démontrer que pour tout entier naturel n : 2 · x n − y n = 5 b Exprimer y n en fonction de n . c En utilisant les congruences modulo 5 , étudier suivant les valeurs de l’entier naturel p le reste de la division euclidienne de 2 p par 5 . d On note d n le PGCD de x n et de y n pour tout entier naturel n . Démontrer que l’on a d n =1 ou d n =5 ; en déduire l’ensemble des entiers naturels n tels que x n et y n soient premiers entre eux. E.3320 On considère la suite u n d’entiers naturels définie par : u 0 = 14 u n +1 = 5 u n − 6 pour tout entier naturel n 1 Calculer u 1 , u 2 , u 3 et u 4 . Quelle conjecture peut-on émettre concernant les deux derniers chiffres de u n ? 2 Montrer que, pour tout entier naturel n : u n +2 ≡ u n ( mod. 4) . En déduire que pour tout entier naturel k : u 2 k ≡ 2 ( mod. 4) et u 2 k +1 ≡ 0 ( mod. 4) . 3 a Montrer par récurrence que, pour tout entier n ∈ N : 2 · u n = 5 n +2 + 3 . b En déduire que, pour tout entier naturel n : 2 u n ≡ 28 ( mod. 100) . 4 Déterminer les deux derniers chiffres de l’écriture déci-male de u n suivant les valeurs de n . 5 Montrer que le PGCD de deux termes consécutifs de la suite u n est constant. Préciser sa valeur. E.3719 Partie A On admet que 1 999 est un entier premier. Déterminer l’ensemble des couples ( a ; b ) d’entiers naturels admettant pour somme 11 994 et pour PGCD 1 999 . Partie B On considère l’équation ( E ) d’inconnu n appartenant à N : ( E ): n 2 − S · n +11 994=0 où S est un entier naturel. On s’intéresse à des valeurs de S telle que ( E ) admette deux solutions dans N . 1 Peut-on déterminer un entier S tel que 3 soit solution de ( E ) ? Si oui, préciser la deuxième solution. 2 Peut-on déterminer un entier S tel que 5 soit solution de ( E ) ? 3 Montrer que tout entier n solution de ( E ) est un diviseur de 11 994 . En déduire toutes les valeurs possibles de S telles que ( E ) admette deux solutions entières. Partie C Comment montrerait-on que 1 999 est un entier premier? Préciser le raisonnement employé? La liste de tous les entiers premiers inférieurs à 100 est pré-cisée ci-dessous : 2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 23 ; 31 ; 37 ; 41 ; 43 ; 47 ; 53 ; 59 61 ; 67 ; 71 ; 73 ; 79 ; 83 ; 89 ; 97 https://chingmath.fr chapExoCorrec/5284 sacados/5284 Asie Juin 2003 4 points chapExoCorrec/5285 sacados/5285 Liban Mai 2003 5 points chapExoCorrec/3320 sacados/3320 chapExoCorrec/3719 sacados/3719
E.3246 Dans cet exercice, on pourra utiliser la proposition : Proposition: ˇ Étant donnés deux entiers naturels, a et b non nuls, si pgcd ( a ; b )=1 alors pgcd ( a 2 ; b 2 )=1 ı Une suite ( S n ) est définie pour n> 0 par : S n = n p =1 p 3 . On se propose de calculer, pour tout entier naturel non nul n , le plus grand commun diviseur de S n et S n +1 . 1 Démontrer que, pour tout n> 0 , on a: S n = n ( n +1) 2 2 . 2 Étude du cas où n est pair. Soit k l’entier naturel non nul tel que n =2 k . a Démontrer que : pgcd ( S 2 k ; S 2 k +1 ) = (2 k + 1) 2 · pgcd ( k 2 ; ( k +1) 2 ) . b Calculer: pgcd ( k ; k +1) . c Calculer: pgcd ( S 2 k ; S 2 k +1 ) . 3 Étude du cas où n est impair. Soit k l’entier naturel non nul tel que n =2 k +1 . a Démontrer que les entiers 2 k +1 et 2 k +3 sont premiers entre eux. b Calculer: pgcd ( S 2 k +1 ; S 2 k +2 ) . 4 Déduire des questions précédentes qu’il existe une unique valeur de n , que l’on déterminera, pour laquelle S n et S n +1 sont premiers entre eux. 2. Théorème de Bezout E.3226 Dans cet exercice, a et b désignent des entiers strictement positifs. 1 a Démontrer que s’il existe deux entiers relatifs u et v tels que a · u + b · v =1 alors les entiers a et b sont pre-miers entre eux. b En déduire que si ( a 2 + a · b − b 2 ) 2 =1 , alors a et b sont premiers entre eux. 2 On se propose de déterminer les couples d’entiers stricte-ment positifs ( a ; b ) tels que ( a 2 + a · b − b 2 ) 2 =1 . Un tel couple sera appelé solution. a Déterminer a lorsque : a = b . b Vérifier que (1 ; 1) , (2 ; 3) et (5 ; 8) sont trois solutions particulières. c Montrer que si ( a ; b ) est solution et si a<b , alors: a 2 − b 2 < 0 . 3 a Montrer que si ( x ; y ) est une solution différente de (1 ; 1) alors ( y − x ; x ) et ( y ; y + x ) sont aussi des solu-tions. b Déduire de 2 b trois nouvelles solutions. 4 On considère la suite d’entiers strictement positifs a n n définie par a 0 = a 1 =1 et pour tout entier n , n 0 : a n +2 = a n +1 + a n . Démontrer que pour tout entier n 0 , ( a n ; a n +1 ) est so-lution. En déduire que les entiers a n et a n +1 sont premiers entre eux. E.3741 1 Montrer que, pour tout entier naturel non nul k et pour tout entier naturel x : ( x − 1) · 1 + x + x 2 + · · · + x k − 1 = x k − 1 Dans toute la suite de l’exercice, on considère un entier a supérieur ou égal à 2 . 2 a Soit n un entier naturel non nul et d un diviseur positif de n : n = d · k Montrer que a d − 1 est un diviseur de a n − 1 . b Déduire de la question précédente que 2 2004 − 1 est di-visible par 7 , par 63 puis par 9 . 3 Soient m et n deux entiers naturels non nuls et d leur pgcd . a On définit m et n par m = d · m et n = d · n . En appli-quant le théorème de Bézout à m et n , montrer qu’il existe des entiers relatifs u et v tels que : m · u − n · v = d . b On suppose u et v strictement positifs. Montrer que : a m · u − 1 − a n · v − 1 · a d = a d − 1 Montrer ensuite que a d − 1 est le pgcd de : a m · u − 1 et a n · v − 1 . c Calculer, en utilisant le résultat précédent le PGCD de : 2 63 − 1 et 2 60 − 1 3. Théorème de Gauss E.3630 Soit ( E ) l’ensemble des entiers naturels écrits, en base 10, sous la forme abba où a est un chiffre supérieur ou égal à 2 et b est un chiffre quelconque. Exemples d’éléments de ( E ) : 2002 ; 3773 ; 9119 . Nombre d’éléments de ( E ) ayant 11 comme plus petit facteur premier 1 a Décomposer 1001 en produit de facteurs premiers. b Montrer que tout élément de ( E ) est divisible par 11 . 2 a Quel est le nombre d’éléments de ( E ) ? b Quel est le nombre d’éléments de ( E ) qui ne sont ni divisibles par 2 ni par 5 ? 3 soit n un élément de ( E ) s’écrivant sous la forme abba . a Montrer que : https://chingmath.fr chapExoCorrec/3246 sacados/3246 chapExoCorrec/3226 sacados/3226 chapExoCorrec/3741 sacados/3741 France Juin 2004 5 points chapExoCorrec/3630 sacados/3630
ˇ n est divisible par 3 équivaut à a + b est divisible par 3 ı b Montrer que : ˇ n est divisible par 7 équivaut à b est divisible par 7 ı 4 Déduire des questions précédentes le nombre d’éléments de ( E ) qui admettent 11 comme plus petit facteur pre-mier. E.3837 Soit A l’ensemble des entiers na-turels de l’intervalle 1 ; 46] . 1 On considère l’équation: ( E ) : 23 · x + 47 · y = 1 où x et y sont des entiers relatifs. a Donner une solution particulière x 0 ; y 0 de ( E ) . b Déterminer l’ensemble des couples ( x ; y ) solutions de ( E ) . c En déduire qu’il existe un unique entier x appartenant à A tel que : 23 · x ≡ 1 ( mod. 47) 2 Soient a et b deux entiers relatifs. a Montrer que si a · b ≡ 0 ( mod. 47) alors: a ≡ 0 ( mod. 47) ou b ≡ 0 ( mod. 47) . b En déduire que si a 2 ≡ 1 ( mod. 47) alors: a ≡ 1 ( mod. 47) ; a ≡ − 1 ( mod. 47) 3 a Montrer que pour tout entier p de A , il existe un entier relatif q tel que : p × q ≡ 1 ( mod. 47) . Pour la suite, on admet que pour tout entier p de A , il existe un unique entier, noté inv ( p ) , appartenant à A tel que : p × inv ( p ) ≡ 1 ( mod. 47) . Par exemple: inv (1) = 1 car 1 × 1 ≡ 1 ( mod. 47) ; inv (2) = 24 car 2 × 24 ≡ 1 ( mod. 47) ; inv (3) = 16 car 3 × 16 ≡ 1 ( mod. 47) . b Quels sont les entiers p de A qui vérifient : p = inv ( p ) c Montrer que : 46! ≡ − 1 ( mod. 47) 4. Equation diophantienne E.3198 Partie A : Question de cours 1 Énoncer le théorème de Bézout et le théorème de Gauss. 2 Démontrer le théorème de Gauss en utilisant le théorème de Bézout. Partie B Il s’agit de résoudre dans Z le système : ( S ) n ≡ 13 ( mod. 19) n ≡ 6 ( mod. 12) 1 Démontrer qu’il existe un couple ( u ; v ) d’entiers relatifs tel que : 19 u + 12 v = 1 (On ne demande pas dans cette question de donner un exemple d’un tel couple) Vérifier que l’entier N =13 × 12 v +6 × 19 u est une solution de ( S ) pour un tel couple. 2 a Soit n 0 une solution de ( S ) , vérifier que le système ( S ) équivaut à: n ≡ n 0 ( mod. 19) n ≡ n 0 ( mod. 12) b Démontrer que le système n ≡ n 0 ( mod. 19) n ≡ n 0 ( mod. 12) équivaut à: n ≡ n 0 ( mod. 12 × 19) . 3 a Trouver un couple ( u ; v ) solution de l’équation 19 u +12 v =1 et calculer la valeur de N correspondante. b Déterminer l’ensemble des solutions de ( S ) (on pourra utiliser la question 2 b ) . 4 Un entier naturel n est tel que lorsqu’on le divise par 12 le reste est 6 et lorsqu’on le divise par 19 le reste est 13 . On divise n par 228=12 × 19 . Quel est le reste r de cette division? E.3258 On rappelle que 2 003 est un entier premier. 1 a Déterminer deux entiers relatifs u et v tels que : 123 u + 2003 v = 1 b En déduire un entier relatif k 0 tel que : 123 k 0 ≡ 1 ( mod. 2003) c Montrer que, pour tout entier relatif x , 123 x ≡ 456 ( mod. 2003) si, et seulement si, x ≡ 456 k 0 ( mod. 2003) d Montrer qu’il existe un unique entier n tel que : 1 n 2002 et 123 n ≡ 456 ( mod. 2003) . 2 Soit a un entier tel que : 1 a 2002 a Déterminer : pgcd ( a ; 2003) En déduire qu’il existe un entier m tel que : a · m ≡ 1 ( mod. 2003) b Montrer que, pour tout entier b , il existe un unique entier x tel que : 0 x 2 002 ; a · x ≡ b ( mod. 2003) https://chingmath.fr chapExoCorrec/3837 sacados/3837 chapExoCorrec/3198 sacados/3198 chapExoCorrec/3258 sacados/3258 France Septembre 2003 5 points
E.3256 Soit l’équation (1) d’inconnue ra-tionnelle x : 78 x 3 + u · x 2 + v · x − 14 = 0 où u et v sont des entiers relatifs. 1 On suppose dans cette question que 14 39 est solution de l’équation (1) . a Prouver que les entiers relatifs u et v sont liés par la relation: 14 u + 39 v = 1129 b Utiliser l’algorithme d’Euclide, en détaillant les di-verses étapes du calcul, pour trouver un couple ( x ; y ) d’entiers relatifs vérifiant l’équation: 14 x + 39 y = 1 Vérifier que le couple ( − 25 ; 9) est solution de cette équation. c En déduire un couple ( u 0 ; v 0 ) solution particulière de l’équation: 14 u + 39 v = 1129 Donner la solution générale de cette équation, c’est-à-dire l’ensemble des couples ( u ; v ) d’entiers relatifs qui la vérifient. d Déterminer, parmi les couples ( u ; v ) précédents, celui pour lequel l’entier u est l’entier naturel le plus petit possible. 2 a Décomposer 78 et 14 en facteurs premiers. En déduire, dans N , l’ensemble des diviseurs de 78 et l’ensemble des diviseurs de 14. b Soit P Q une solution rationnelle de l’équation (1) d’inconnue x : 78 x 3 + ux 2 + vx − 14 = 0 où u et v sont des entiers relatifs. Montrer que si P et Q sont des entiers relatifs premiers entre eux, alors P divise 14 et Q divise 78. c En déduire le nombre de rationnels, non entiers, pou-vant être solutions de l’équation (1) et écrire, parmi ces rationnels, l’ensemble de ceux qui sont positifs. E.3477 Les parties A et B sont indépen-dantes. Partie A On considère l’équation ( E ): 7 x − 6 y =1 où x et y sont des entiers naturels. 1 Donner une solution particulière de l’équation ( E ) . 2 Déterminer l’ensemble des couples d’entiers naturels so-lutions de l’équation ( E ) . Partie B Dans cette partie, on se propose de déterminer les couples ( n ; m ) d’entiers naturels non nul 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.3905 Les questions 1 et 2 sont in-dépendantes. Soit n un entier naturel non nul. 1 On considère l’équation notée ( E ) : 3 x + 7 y = 10 2 n où x et y sont des entiers relatifs. a Déterminer un couple ( u ; v ) d’entiers relatifs tels que : 3 · u + 7 · v = 1 En déduire une solution particulière ( x 0 ; y 0 ) de l’équation ( E ) . b Déterminer l’ensemble des couples d’entiers relatifs ( x ; y ) solutions de ( E ) . 2 On considère l’équation notée ( G ) : 3 x 2 + 7 y 2 = 10 2 n où x et y sont des entiers relatifs. a Montrer que : 100 ≡ 2 ( mod. 7) . Démontrer que si ( x ; y ) est solution de ( G ) alors: 3 x 2 ≡ 2 n ( mod. 7) . b Reproduire et compléter le tableau suivant : Reste de la division euclidienne de x par 7 0 1 2 3 4 5 6 Reste de la division euclidienne de 3 x 2 par 7 c Démontrer que 2 n est congru à 1 , 2 ou 4 modulo 7 . En déduire que l’équation ( G ) n’admet pas de solution. https://chingmath.fr chapExoCorrec/3256 sacados/3256 Antilles-Guyane Septembre 2003 4 points chapExoCorrec/3477 sacados/3477 chapExoCorrec/3905 sacados/3905
E.5432 Partie A - Restitution organ-isée des connaissances Prérequis: on rappelle ci-dessous le théorème de Bézout et le théorème de Gauss. Théorème de Bézout: Deux entiers relatifs a et b sont premiers entre eux si, et seulement si, il existe un couple ( u ; v ) d’entiers relatifs vérifiant a · u + b · v =1 . Théorème de Gauss: Soient a , b , c des entiers relatifs. Si a divise le produit b · c et si a et b sont premiers entre eux, alors a divise c 1 En utilisant le théorème de Bézout, démontrer le théorème de Gauss. 2 Soient p et q deux entiers naturels tels que p et q sont premiers entre eux. Déduire du théorème de Gauss que, si a est un entier relatif, tel que a ≡ 0 ( mod. p ) et a ≡ 0 ( mod. q ) , alors a ≡ 0 ( mod. pq ) Partie B On se propose de déterminer l’ensemble S des entiers relatifs n vérifiant le système : n ≡ 9 ( mod. 17) n ≡ 3 ( mod. 5) 1 Recherche d’un élément de S . On désigne par ( u ; v ) un couple d’entiers relatifs tels que : 17 · u +5 · v =1 a Justifier l’existence d’un tel couple ( u ; v ) . b On pose : n 0 =3 × 17 u +9 × 5 v . Démontrer que n 0 appartient à S . c Donner un exemple d’entier n 0 appartenant à S . 2 Caractérisation des éléments de S . a Soit n un entier relatif appartenant à S . Démontrer que : n − n 0 ≡ 0 ( mod. 85) . b En déduire qu’un entier relatif n appartient à S si, et seulement, s’il peut s’écrire sous la forme n =43+85 k où k est un entier relatif. 3 Application. Zoé sait qu’elle a entre 300 et 400 jetons. Si elle fait des tas de 17 jetons, il lui en reste 9 . Si elle fait des tas de 5 jetons, il lui en reste 3 . Combien a-t-elle de jetons? E.3322 1 a Quel est le reste de la division euclidienne de 6 10 par 11 ? Justifier. b Quel est le reste de la division euclidienne de 6 4 par 5? Justifier. c En déduire les deux congruences : 6 40 ≡ 1 ( mod. 11) ; 6 40 ≡ 1 ( mod. 5) . d Démontrer que 6 40 − 1 est divisible par 55 . 2 Dans cette question x et y désignent des entiers relatifs. a Montrer que l’équation: ( E ): 65 · x − 40 · y =1 n’a pas de solution. b Montrer que l’équation: ( E ): 17 · x − 40 · y =1 admet au moins une solution. c Déterminer à l’aide de l’algorithme d’Euclide un cou-ple d’entiers relatifs solutions de l’équation ( E ) . d Résoudre l’équation ( E ) . En déduire qu’il existe un unique naturel x 0 inférieur à 40 tel que : 17 x 0 ≡ 1 ( mod. 40) 3 Pour tout entier naturel a , démontrer que : Si a 17 ≡ b ( mod. 55) a 40 ≡ 1 ( mod. 55) alors b 33 ≡ a ( mod. 55) 5. Problème de codage E.5456 Partie A : Restitution organisée de connaissance Soit a , b , c , d des entiers relatifs et n un entier naturel non nul. Montrer que si a ≡ b ( mod. n ) et si c ≡ d ( mod. n ) alors ac ≡ bd ( mod. n ) . Partie B: Inverse de 23 modulo 26 On considère l’équation: ( E ): 23 x − 26 y =1 où x et y désig-nent deux entiers relatifs. 1 Vérifier que le couple ( − 9 ; − 8) est solution de l’équation ( E ) . 2 Résoudre alors l’équation ( E ) . 3 En déduire un entier a tel que : 0 a 25 ; 23 a ≡ 1 ( mod. 26) Partie C : Chiffrement de Hill On veut coder un mot de deux lettres selon la procédure suiv- ante : Étape 1 Chaque lettre du mot est remplacée par un entier en utilisant le tableau ci-dessous : 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 obtient un couple d’entiers ( x 1 ; x 2 ) où x 1 correspond à la première lettre du mot et x 2 correspond à la deux-ième lettre du mot. Étape 2 ( x 1 ; x 2 ) est transformé en ( y 1 ; y 2 ) tel que : ( S 1 ) : y 1 ≡ 11 x 1 + 3 x 2 ( mod. 26) y 2 ≡ 7 x 1 + 4 x 2 ( mod. 26) avec 0 y 1 25 et 0 y 2 25 . Étape 3 ( y 1 ; y 2 ) est transformé en un mot de deux let-tres en utilisant le tableau de correspondance donné dans https://chingmath.fr chapExoCorrec/5432 sacados/5432 chapExoCorrec/3322 sacados/3322 chapExoCorrec/5456 sacados/5456
l’étape 1 . Exemple : TE  mot en clair étape 1 = ⇒ (19 ; 4) étape 2 = ⇒ (13 ; 19) étape 3 = ⇒ NT  mot codé 1 Coder le mot ST . 2 On veut maintenant déterminer la procédure de dé-codage : a Montrer que tout couple ( x 1 ; x 2 ) vérifiant les équations du système ( S 1 ) , vérifie les équations du système : ( S 2 ) : 23 x 1 ≡ 4 y 1 + 23 y 2 ( mod. 26) 23 x 2 ≡ 19 y 1 + 11 y 2 ( mod. 26) b À l’aide de la partie B , montrer que tout couple ( x 1 ; x 2 ) vérifiant les équations du système ( S 2 ) , véri-fie les équations du système : ( S 3 ) : x 1 ≡ 16 y 1 + y 2 ( mod. 26) x 2 ≡ 11 y 1 + 5 y 2 ( mod. 26) c Montrer que tout couple ( x 1 ; x 2 ) vérifiant les équations du système ( S 3 ) , vérifie les équations du système ( S 1 ) . d Décoder le mot Y J E.3324 Partie A On considère l’équation ( E ): 11 x − 26 y =1 , où x et y désignent deux nombres entiers relatifs. 1 Vérifier que le couple ( − 7 ; − 3) est solution de ( E ) . 2 Résoudre alors l’équation ( E ) . 3 En déduire le couple d’entiers relatifs ( u ; v ) solution de ( E ) tel que : 0 u 25 . Partie B On assimile chaque lettre de l’alphabet à un nombre entier comme l’indique le tableau ci-dessous : 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 ˇ code ı tout nombre entier x compris entre 0 et 25 de la façon suivante : On calcule 11 x +8 . On calcule le reste de la division euclidienne de 11 x +8 par 26, que l’on appelle y . x est alors ˇ codé ı par y . Ainsi, par exemple, la lettre L est assimilée à l’entier 11 ; 11 × 11+8=129 or 129 ≡ 25 ( mod. 26) ; 25 est le reste de la division euclidienne de 129 par 26. À l’entier 25 correspond la lettre Z . La lettre L est donc codée par la lettre Z . 1 Coder la lettre W . 2 Le but de cette question est de déterminer la fonction de décodage. a Montrer que pour tous nombres entiers relatifs x et j , on a: 11 · x ≡ j ( mod. 26) équivaut à x ≡ 19 · j ( mod. 26) . b En déduire un procédé de décodage. c Décoder la lettre W . 6. Arithmétique et géométrie E.3264 1 a Soit p un entier naturel. Montrer que l’un des trois entiers p , p +10 et p +20 , et un seulement est divisible par 3. b Les entiers naturels a , b et c sont dans cet ordre les trois premiers termes d’une suite arithmétique de rai-son 10. Déterminer ces trois entiers sachant qu’ils sont premiers. 2 Soit E l’ensemble des triplets d’entiers relatifs ( u ; v ; w ) tels que : 3 · u + 13 · v + 23 · w = 0 a Montrer que pour un tel triplet: v ≡ w ( mod. 3) b On pose v =3 k + r et w =3 k + r où k , k et r sont des entiers relatifs et 0 r 2 . Montrer que les éléments de E sont de la forme : − 13 k − 23 k − 12 r ; 3 k + r ; 3 k + r c L’espace est rapporté à un repère orthonormé d’origine O et soit P le plan d’équation 3 x +13 y +23 z =0 . Déterminer l’ensemble des points M à coordonnées ( x ; y ; z ) entières relatives appartenant au plan P et situés à l’intérieur du cube de centre O , de côté 5 et dont les arêtes sont parallèles aux axes. https://chingmath.fr chapExoCorrec/3324 sacados/3324 Antilles-Guyane Juin 2008 5 points chapExoCorrec/3264 sacados/3264
E.3325 Soit a et b deux entiers naturels non nuls ; on appelle ˇ réseau ı associé aux entiers a et b l’ensemble des points du plan, muni d’un repère orthonormé, dont les coordonnées ( x ; y ) sont des entiers vérifiant les con-ditions : 0 x a ; 0 y b On note R a,b ce réseau. Le but de l’exercice est de relier certaines propriétés arithmé-tiques des entiers x et y à des propriétés géométriques des points correspondants du réseau. A - Représentation graphique de quelques ensemble Dans cette question, les réponses sont attendues sans explica-tion, sous la forme d’un graphique qui sera dûment complété sur la feuille annexe à rendre avec la copie. Représenter graphiquement les points M ( x ; y ) du réseau R 8 , 8 vérifiant : 1 x ≡ 2 ( mod. 3) et y ≡ 1 ( mod. 3) , sur le graphique 1 de la feuille annexe. 2 x + y ≡ 1 ( mod. 3) , sur le graphique 2 de la feuille annexe. 3 x ≡ y ( mod. 3) , sur le graphique 3 de la feuille annexe. B - Résolution d’une équation On considère l’équation ( E ): 7 x − 4 y =1 , où les inconnues x et y sont des entiers relatifs. 1 Déterminer un couple d’entiers relatifs ( x 0 ; y 0 ) solution de l’équation ( E ) . 2 Déterminer l’ensemble des couples d’entiers relatifs solu-tions de l’équation ( E ) . 3 Démontrer que l’équation ( E ) admet une unique solu-tion ( x ; y ) pour laquelle le point M ( x ; y ) correspondant appartient au réseau R 4 , 7 . C - Une propriété des points situés sur la diagonale du réseau. Si a et b sont deux entiers naturels non nuls, on considère la diagonale [ OA ] du réseau R a,b avec O (0 ; 0) et A ( a ; b ) . 1 Démontrer que les points du segment [ OA ] sont carac-térisés par les conditions : 0 x a ; 0 y b ; a · y = b · x 2 Démontrer que si a et b sont premiers entre eux, alors les points O et A sont les seuls points du segment [ OA ] appartenant au réseau R a,b . 3 Démontrer que si a et b ne sont pas premiers entre eux, alors le segment [ OA ] contient au moins un autre point du réseau. (On pourra considérer le PGCD d des entiers a et b et poser a = d · a et b = d · b ) Graphique 1 Graphique 2 Graphique 3 https://chingmath.fr chapExoCorrec/3325 sacados/3325 Asie Juin 2008 5 points -123456789I-123456789JO -123456789I-123456789JO -123456789I-123456789JO
7. Arithmétique et suite E.3254 On considère la suite u n d’entiers naturels définie par : u 0 = 14 u n +1 = 5 u n − 6 pour tout entier naturel n 1 Calculer u 1 , u 2 , u 3 et u 4 . Quelle conjecture peut-on émettre concernant les deux derniers chiffres de u n ? 2 Montrer que, pour tout entier naturel n : u n +2 ≡ u n ( mod. 4) . En déduire que pour tout entier naturel k : u 2 k ≡ 2 ( mod. 4) et u 2 k +1 ≡ 0 ( mod. 4) . 3 a Montrer par récurrence que, pour tout n ∈ N : 2 u n = 5 n +2 + 3 . b En déduire que, pour tout entier naturel n : 2 u n ≡ 28 ( mod. 100) . 4 Déterminer les deux derniers chiffres de l’écriture déci-male de u n suivant les valeurs de n . 5 Montrer que le PGCD de deux termes consécutifs de la suite ( u n ) est constant. Préciser sa valeur. E.3574 1 Calculer le PGCD de 4 5 − 1 et de 4 6 − 1 . Soit u la suite numérique définie par : u 0 = 0 u 1 = 1 u n +2 = 5 · u n +1 − 4 · u n pour tout entier naturel n 2 Calculer les termes u 2 , u 3 et u 4 de la suite u . 3 a Montrer que la suite u vérifie, pour tout entier na-turel n : u n +1 = 4 · u n + 1 b Montrer que, pour tout entier naturel n , u n est un entier naturel. c En déduire, pour tout entier naturel n , le PGCD de u n et u n +1 . 4 Soit v la suite définie pour tout entier naturel n par : v n = u n + 1 3 a Montrer que v est une suite géométrique dont on déter-minera la raison et le premier terme v 0 . b Exprimer v n puis u n en fonction de n . c Déterminer, pour tout entier naturel n , le PGCD de 4 n +1 − 1 et de 4 n − 1 . E.6252 On considère la fonction f d’un algorithme prenant pour argument deux entiers naturels A et B vérifiant A < B : Fonction f(A,B) D ← B − A Tant que D>0 B ← de A A ← de D Si B>A Alors D ← de B − A Sinon D ← de A − B Fin Si Fin Tant que Renvoyer A 1 On appelle la fonction f avec pour valeurs des arguments : A =12 et B =14 . On complétera le tableau ci-dessous en y indiquant les valeurs successives prises par les variables A , B et D au cours de l’appel à cette fonction. A B D 12 14 2 L’appel à la fonction f calcule la valeur du PGCD des entiers A et B . En entrant A =221 et B =331 , l’appel à la fonction f ren-voie la valeur 1 . a justifier qu’il existe des couples ( x ; y ) d’entiers relatifs solutions de l’équation: ( E ) : 221 · x − 331 · y = 1 b Vérifier que le couple (3 ; 2) est une solution de l’équation ( E ) . En déduire l’ensemble des couples ( x ; y ) d’entiers re-latifs solutions de l’équation ( E ) . 3 On considère les suites d’entiers naturels u n et v n définies pour tout entier naturel n par : u n = 2 + 221 · n ; v 0 = 3 v n +1 = v n + 331 a Exprimer v n en fonction de l’entier naturel n . b Déterminer tous les couples d’entiers naturels ( p ; q ) tels que : u p = v q ; 0 p 500 ; 0 q 500 https://chingmath.fr chapExoCorrec/3254 sacados/3254 chapExoCorrec/3574 sacados/3574 chapExoCorrec/6252 sacados/6252
8. Exercices non-classés E.1604 Pour chacune des cinq proposi-tions suivantes, indiquer si elle est vraie ou fausse et donner une démonstration de la réponse choisie. Une réponse non démontrée ne rapporte aucun point, Proposition 1: Pour tout entier naturel n , 3 divise le nom-bre entier 2 2 n − 1 Proposition 2: Si un entier relatif x est solution de l’équation x 2 + x ≡ 0 ( mod. 6) alors x ≡ 0 ( mod. 3) Proposition 3: L’ensemble des couples d’entiers relat-ifs ( x ; y ) solutions de l’équation 12 · x − 5 · y =3 est l’ensemble des couples (4+10 · k ; 9+24 · k ) où k ∈ Z Proposition 4: Il existe un seul couple ( a ; b ) de nombres entiers naturels, tel que : a<b et PPCM ( a ; b ) − PGCD ( a ; b )=1 . Deux entiers naturels M et N sont tels que M a pour écriture abc en base dix et N a pour écriture bca en base dix. Proposition 5: Si l’entier M est divisible par 27 alors l’entier M − N est aussi divisible par 27 . E.3133 1 On considère l’équation: ( E ) : 17 x − 24 y = 9 où ( x ; y ) est un couple d’entiers relatifs. a Vérifier que le couple (9 ; 6) est solution de l’équation ( E ) . b Résoudre l’équation ( E ) . 2 Dans une fête foraine, Jean s’installe dans un manège circulaire représenté par le schéma de l’annexe 2. Il peut s’installer sur l’un des huit points indiqués sur le cercle. Le manège comporte un jeu qui consiste à attraper un pompon qui, se déplace sur un câble formant un carré dans lequel est inscrit le cercle. Le manège tourne dans le sens des aiguilles d’une montre, à la vitesse constante. Il fait un tour à vitesse constante. Il fait un tour en 24 secondes. Le pompon se déplace dans le même sens à vitesse constante. Il fait un tour en 17 secondes. Pour gagner, Jean doit attraper le pompon, et il ne peut le faire qu’aux points de contact qui sont notés A , B , C et D sur le dessin. À l’instant t =0 , Jean part du point H en même temps que le pompon part du point A . a On suppose qu’à un certain instant t jean attrape le pompon en A . Jean a déjà pu passer un certain nom-bre de fois en A sans y trouver le pompon. À l’instant t , on note y le nombre de tours effectués depuis son premier passage en A et x le nombre de tours effec-tués par le pompon. Montrer que ( x ; y ) est solution de l’équation ( E ) de la question 1. b Jean a payé pour 2 minutes ; aura-t-il le temps d’attraper le pompon? c Montrer, qu’en fait, il n’est possible d’attraper le pom-pon qu’au point A . d Jean part maintenant du point E . Aura-t-il le temps d’attraper le pompon en A avant les deux minutes. https://chingmath.fr chapExoCorrec/1604 sacados/1604 Polynesie Juin 2006 5 pionts chapExoCorrec/3133 sacados/3133 ABCDEFGH
E.6249 Partie A Le but de cette partie est de démontrer que l’ensemble des entiers premiers est infini en raisonnant par l’absurde. 1 On suppose qu’il existe un nombre fini d’entiers premiers notés p 1 , p 2 , . . . , p n . On considère l’entier E produit de tous les entiers pre-miers augmentés de 1 : E = p 1 × p 2 × · · · × p n + 1 Démontrer que E est un entier supérieur ou égal à 2 , et que E est premier avec chacun des entiers p 1 , p 2 , . . . , p n . 2 En utilisant le fait que E admet un diviseur premier, con-clure. Partie B Pour tout entier naturel k 2 , on pose : M k =2 k − 1 . On dit que M k est le k -ième nombre de Mersenne. 1 a Reproduire et compléter le tableau suivant, qui donne quelques valeurs de M k : k 2 3 4 5 6 7 8 9 10 M k b D’après le tableau précédent, si k est un entier premier, peut-on conjecturer que l’entier M k est premier? 2 Soient p et q deux entiers naturels non nuls. a Justifier l’égalité: 1 + 2 p + 2 p 2 + · · · + 2 p q − 1 = 2 p q − 1 2 p − 1 b En déduire que 2 p · q − 1 est divisible par 2 p − 1 . c En déduire que si un entier k supérieur ou égal à 2 n’est pas premier, alors M k ne l’est pas non plus. 3 a Prouver que le nombre de Mersenne M 11 n’est pas premier. b Que peut-on en déduire concernant la conjecture de la question 1 b ? Partie C Le test de Lucas-Lehmer permet de déterminer si un nom-bre de Mersenne donné est premier. Ce test utilise la suite numérique u n définie par u 0 =4 et pour tout entier naturel n : u n +1 = u n 2 − 2 Si n est un entier naturel supérieur ou égal à 2 , le test per-met d’affirmer que l’entier M n est premier si, et seulement si, u n − 2 ≡ 0 ( mod. M n ) . Cette propriété est admise dans la suite. 1 Utiliser le test de Lucas-Lehmer pour vérifier que le nom-bre de Mersenne M 5 est premier. 2 La fonction de l’algorithme suivant prend pour argument un entier n supérieur ou égal à 3 et doit renvoyer 1 si le nombre de Mersenne M n est premier et 0 sinon, en util-isant le test de Lucas-Lehmer. Fonction f(n) u ← 4 M ← ... Pour i allant de 1 à ... u ← ... Fin Pour Si M divise u Alors Renvoyer ...... Sinon Renvoyer ...... Fin Si Recopier et compléter le code de la fonction f de façon à ce qu’il remplisse la condition voulue. E.3552 Partie I Soit x un nombre réel. 1 Montrer que : x 4 +4= x 2 +2 2 − 4 · x 2 . 2 En déduire que x 4 +4 peut s’écrire comme produit de deux trinômes à coefficients entiers. Partie II Soit n un entier naturel supérieur ou égal à 2 . On considère les entiers : A = n 2 − 2 n +2 ; B = n 2 +2 n +2 et d leur PGCD . 1 Montrer que n 4 +4 n’est pas premier. 2 Montrer que, tout diviseur de A qui divise n , divise 2 . 3 Montrer que, tout diviseur commun de A et de B , divise 4 n . 4 Dans cette question, on suppose que n est impair. a Montrer que A et B sont impairs. En déduire que d est impair. b Montrer que d divise n . c En déduire que d divise 2 , puis, que A et B sont pre-miers entre eux. 5 On suppose maintenant que n est pair. a Montrer que 4 ne divise pas n 2 − 2 n +2 . b Montrer que d est de la forme d =2 · p , où p est impair. c Montrer que p divise n . En déduire que d =2 . (On pourra s’inspirer de la démonstration utilisée à la ques-tion 4 ) . https://chingmath.fr chapExoCorrec/6249 sacados/6249 Asie Juin 2014 chapExoCorrec/3552 sacados/3552
E.6928 Pour tout entier naturel n non nul, on appelle S ( n ) le nombre égal à la somme des diviseurs positifs de n . 1 Vérifier que S (6)=12 et calculer S (7) . 2 a Démontrer que, pour tout entier naturel n supérieur ou égal à 2 : S ( n ) 1+ n b Quels sont les entiers naturels n tels que S ( n )=1+ n ? 3 On suppose dans cette question que n s’écrit p × q où p et q sont des entiers premiers distincts. a Démontrer que : S ( n )= 1+ p 1+ q . b On considère la proposition suivante : ˇ Pour tous entiers naturels n et m non nuls distincts, S n × m = S n × S m ı Cette proposition est-elle vraie ou fausse? Justifier. 4 On suppose dans cette question que l’entier n s’écrit p k , où p est un entier premier et k un entier naturel non nul. a Quels sont les diviseurs de n ? b En déduire que : S ( n )= 1 − p k +1 1 − p . 5 On suppose dans cette question que n s’écrit p 13 × q 7 , où p et q sont des entiers premiers distincts. a Soit m un entier naturel. Démontrer que m divise n si, et seulement si, il existe deux entiers s et t avec 0 s 13 et 0 t 7 tels que m = p s × q t . b Démontrer que : S ( n )= 1 − p 14 1 − p × 1 − q 8 1 − q E.6946 Pour tout couple d’entiers relat-ifs non nuls ( a ; b ) , on note pgcd ( a ; b ) le plus grand diviseur commun de a et b . Le plan est muni d’un repère O ; −→ i ; −→ j . 1 Exemple. Soit Δ 1 la droite d’équation : y = 5 4 · x − 2 3 a Montrer que si ( x ; y ) est un couple d’entiers relatifs alors l’entier 15 · x − 12 · y est divisible par 3 . b Existe-t-il au moins un point de la droite Δ 1 dont les coordonnées sont deux entiers relatifs? Justifier. Généralisation: On considère désormais une droite Δ d’équation : y = m n · x − p q où m , n , p et q sont des entiers relatifs non nuls tels que : pgcd ( m ; n ) = pgcd ( p ; q ) =1 Ainsi, les coefficients de l’équation ( E ) sont des fractions ir-réductibles et on dit que Δ est une droite rationnelle. Le but de l’exercice est de déterminer une condition nécessaire et suffisante sur m , n , p et q pour qu’une droite rationnelle Δ comporte au moins un point dont les coordonnées sont deux entiers relatifs. 2 On suppose ici que la droite Δ comporte un point de coordonnées x 0 ; y 0 où x 0 et y 0 sont des entiers relatifs. a En remarquant que l’entier n · y 0 − m · x 0 est un entier relatif, démontrer que q divise le produit n · p . b En déduire que q divise n . 3 Réciproquement, on suppose que q divise n , et on souhaite trouver un couple x 0 ; y 0 d’entiers relatifs tels que : y 0 = m n · x 0 − p q . a On pose n = q · r , où r est un entier relatif non nul. Dé-montrer qu’on peut trouver deux entiers relatifs u et v tels que : q · r · u − m · v =1 . b En déduire qu’il existe un couple ( x 0 ; y 0 ) d’entiers re-latifs tels que : y 0 = m n · x 0 − p q 4 Soit Δ la droite d’équation y = 3 8 · x − 7 4 . Cette droite possède-t-elle un point dont les coordonnées sont des en-tiers relatifs? Justifier. 5 On considère la fonction f d’un algorithme prenant pour argument les entiers M , N , P et Q . De plus, on suppose que les arguments passés lors de l’appel à la fonction f vérifie: pgcd ( M ; N )= pgcd ( P ; Q )=1 Fonction f(M,N,P,Q) Si Q divise N Alors X ← 0 Tant que M N · X − P Q n’est pas entier et − M N · X − P Q n’est pas entier X ← X+1 Fin Tant que Si M N X − P Q est entier Alors https://chingmath.fr chapExoCorrec/6928 sacados/6928 chapExoCorrec/6946 sacados/6946
Renvoyer X ; M N · X − P Q Sinon Renvoyer − X ; M N · X − P Q Fin Si Sinon Renvoyer "Pasde solution" Fin si a Justifier que l’appel à la fonction f se termine pour toutes valeurs passées en argument de M , N , P , Q , en-tiers relatifs non nuls vérifiant : pgcd ( M ; N ) = pgcd ( P ; Q ) = 1 . b Que permet-il d’obtenir? E.3551 Soit p un entier premier donné. On se propose d’étudier l’existence de couples ( x ; y ) d’entier naturels strictement positifs vérifiant l’équation: ( E ) : x 2 + y 2 = p 2 1 On pose p =2 . Montrer que l’équation ( E ) est sans solu-tion. On suppose désormais p =2 et que le couple ( x ; y ) est solution de l’équation ( E ) . 2 Le but de cette question est de prouver que x et y sont premiers entre eux. a Montrer que x et y sont de parités différentes. b Montrer que x et y ne sont pas divisibles par p . c En déduire que x et y sont premiers entre eux. 3 On suppose maintenant que p est une somme de deux carrés non nuls, c’est-à-dire : p = u 2 + v 2 où u et v sont deux entiers naturels strictement positifs. a Vérifier qu’alors le couple ( | u 2 − v 2 | ; 2 · u · v ) est solution de l’équation ( E ) . b Donner une solution de l’équation ( E ) lorsque p =5 puis lorsque p =13 . 4 On se propose enfin de vérifier sur deux exemples, que l’équation ( E ) est impossible lorsque p n’est pas la somme de deux carrés. a p =3 et p =7 sont-ils somme de deux carrés? b Démontrer que les équations x 2 + y 2 =9 et x 2 + y 2 =49 n’admettent pas de solution en entiers naturels stricte-ment positifs. E.5862 On note E l’ensemble des vingt-sept nombres entiers compris entre 0 et 26 . On note A l’ensemble dont les éléments sont les vingt-six let-tres de l’alphabet et un séparateur entre deux mots, noté ˇ ? ı considéré comme un caractère. Pour coder les éléments de A , on procède de la façon suivante : Premièrement : on associe à chacune des lettres de l’alphabet, rangées par ordre alphabétique, un nombre entier naturel compris entre 0 et 25 , rangés par ordre croissant. On a donc : a ↦−→ 0 ; b ↦−→ 1 ; . . . ; z ↦−→ 25 . On associe au séparateur ˇ ? ı le nombre entier 26 . a b c d e f g h i j k l m n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 o p q r s t u v w x y z ? 14 15 16 17 18 19 20 21 22 23 24 25 26 On dit que a a pour rang 0 , b a pour rang 1 ,. . . , z a pour rang 25 et le séparateur ˇ ? ı a pour rang 26 . Deuxièmement : à chaque élément x de E , l’application g associe le reste de la division euclidienne de 4 x +3 par 27 . On remarquera que, pour tout x de E , g ( x ) appartient à E . Troisièmement : le caractère initial est alors remplacé par le caractère de rang g ( x ) . Exemple: s ↦−→ 18 ; g (18) = 21 ; 21 ↦−→ v . Donc, la lettre s est remplacée lors du codage par la lettre v . 1 Trouver tous les entiers x de E tel que g ( x )= x , c’est-à-dire invariants par l’application g . En déduire tous les caractères invariants dans ce codage. 2 Démontrer que, pour tout entier naturel x appartenant à E et tout entier naturel y appartenant à E : Si y ≡ 4 x +3 ( mod. 27) alors x ≡ 7 y +6 ( mod. 27) En déduire que deux caractères distincts sont codés par deux caractères distincts. 3 Proposer une méthode de décodage. 4 Décoder le mot ˇ vfv ı. https://chingmath.fr chapExoCorrec/3551 sacados/3551 chapExoCorrec/5862 sacados/5862
E.6903 Les entiers naturels 1 , 11 , 111 , 1111 . . . sont des rep-units. On appelle ainsi les entiers na-turels ne s’écrivant qu’avec des 1 . Pour tout entier naturel p non nul, on note N p le rep-unit s’écrivant avec p fois le chiffre 1 : N p = 11 : : : 1  p répétitions du chiffre 1 = k = p − 1 k =0 10 k Dans tout l’exercice, p désigne un entier naturel non-nul. L’objet de cet exercice est d’étudier quelques propriétés des rep-units. Partie A : divisibilité des rep-units dans quelques cas particuliers 1 Montrer que N p n’est divisible ni par 2 ni par 5 . 2 Dans cette question, on étudie la divisibilité de N p par 3 . a Prouver que, pour tout entier naturel j : 10 j ≡ 1 ( mod. 3) b En déduire que N p ≡ p ( mod. 3) . c Déterminer une condition nécessaire et suffisante pour que le rep-unit N p soit divisible par 3 . 3 Dans cette question, on étudie la divisibilité N p par 7 . a Recopier et compléter le tableau des congruences ci-dessous, où a est l’unique entier relatif appartenant à: − 3 ; − 2 ; − 1 ; 0 ; 1 ; 2 ; 3 tel que : 10 m ≡ a ( mod. 7) On ne demande pas de justification . m 0 1 2 3 4 5 6 a b Soit p un entier naturel non nul. Montrer que 10 p ≡ 1 ( mod. 7) si, et seulement si, p est un multiple de 6 . On pourra utiliser la division euclidienne de p par 6 . c Justifier que, pour tout entier naturel p non-nul : N p = 10 p − 1 9 d Démontrer que ˇ 7 divise N p ı est équivalent à ˇ 7 divise 9 · N p ı. e En déduire que N p est divisible par 7 si, et seulement si, p est un multiple de 6 . Partie B: un rep-unit strictement supérieur à 1 n’est jamais un carré parfait 1 Soit n un entier naturel supérieur ou égal à 2 . On suppose que l’écriture décimale de n 2 se termine par le chiffre 1 , c’est-à-dire n 2 ≡ 1 ( mod. 10) a Recopier et compléter le tableau de congruences ci-dessous : n ≡ : : : [10] 0 1 2 3 4 5 6 7 8 9 n 2 ≡ : : : [10] b En déduire qu’il existe un entier naturel m tel que : n = 10 · m + 1 ou n = 10 · m − 1 . c Conclure que : n 2 ≡ 1 ( mod. 20) . 2 Soit p un entier naturel supérieur ou égal à 2 . Quel est le reste de la division euclidienne de N p par 20 ? 3 En déduire que, pour p entier naturel supérieur ou égal à 2 , le rep-unit N p n’est pas le carré d’un entier. E.8134 À toute lettre de l’alphabet, on as-socie un nombre entier x compris entre 0 et 25 comme indiqué dans le tableau ci-dessous : Lettre A B C D E F G H I J K L M x 0 1 2 3 4 5 6 7 8 9 10 11 12 Lettre N O P Q R S T U V W X Y Z x 13 14 15 16 17 18 19 20 21 22 23 24 25 Le ˇ chiffre de RABIN ı est un dispositif de cryptage asymétrique inventé en 1979 par l’informaticien Michael Ra-bin. Alice veut communiquer de manière sécurisée en utilisant ce cryptosystème. Elle choisit deux nombres distincts p et q . Ce couple de nombres est sa clé privée qu’elle garde secrète. Elle calcule ensuite n = p × q et elle choisit un nombre entier naturel B tel que 0 B n − 1 . Si Bob veut envoyer un message secret à Alice, il le code lettre par lettre. Le codage d’une lettre représentée par le nombre entier x est le nombre y tel que : y ≡ x x + B ( mod. n ) avec 0 y n Dans tout l’exercice, on prend p =3 , q =11 donc n = p × q =33 et B =13 . Partie A : Cryptage Bob veut envoyer le mot ˇ NO ı à Alice. 1 Montrer que Bob code la lettre ˇ N ı avec le nombre 8 . 2 Déterminer le nombre qui code la lettre ˇ O ı. Partie B: Décryptage Alice a reçu un message crypté qui commence par le nombre 3 . Pour décoder ce premier nombre, elle doit déterminer le nom-bre entier x tel que : x x +3 ≡ 3 ( mod. 33) 0 x< 26 1 Montrer que x · x +13 ≡ 3 ( mod. 33) équivaut à: x + 23 2 ≡ 4 ( mod. 33) . 2 a Montrer que si x +23 2 ≡ 4 ( mod. 33) alors le sys-tème d’équations x + 23 2 ≡ 4 ( mod. 3) x + 23 2 ≡ 4 ( mod. 11) est vérifié. b Réciproquement, montrer que si x + 23 2 ≡ 4 ( mod. 3) x + 23 2 ≡ 4 ( mod. 11) alors x +23 2 ≡ 4 ( mod. 33) c En déduire que : x · x +13 ≡ 3 ( mod. 33) ⇐⇒ x +23 2 ≡ 1 ( mod. 3) x +23 2 ≡ 4 ( mod. 11) 3 a Déterminer les nombres entiers naturels a tels que 0 a< 3 et a 2 ≡ 1 ( mod. 3) . b Déterminer les nombres entiers naturels b tels que https://chingmath.fr chapExoCorrec/6903 sacados/6903 sacados/8134
0 b< 11 et b 2 ≡ 4 ( mod. 11) . 4 a En déduire que x · x +13 ≡ 3 ( mod. 33) équivaut aux quatre systèmes suivants : x ≡ 2 ( mod. 3) x ≡ 8 ( mod. 11) ou x ≡ 0 ( mod. 3) x ≡ 1 ( mod. 11) ou x ≡ 2 ( mod. 3) x ≡ 1 ( mod. 11) ou x ≡ 0 ( mod. 3) x ≡ 8 ( mod. 11) b On admet que chacun de ces systèmes admet une unique solution entière x telle que 0 x< 33 . Déterminer, sans justification, chacune de ces solu-tions. 5 Compléter l’algorithme ci-dessous pour qu’il affiche les quatre solutions trouvées dans la question précédente. Pour...allant de...à... Si le reste de la division de...par...est égal à...alors Afficher ... Fin Si Fin Pour 6 Alice peut-elle connaître la première lettre du message envoyé par Bob? Le ˇ chiffre de RABIN ı est-il utilisable pour décoder un message lettre par lettre? E.8140 Le but de cet exercice est d’envisager une méthode de cryptage à clé publique d’une information numérique, appelée système RSA, en l’honneur des mathématiciens Ronald Rivest, Adi Shamir et Leonard Adleman, qui ont inventé cette méthode de cryptage en 1977 et l’ont publiée en 1978 . Les questions 1 et 2 sont des questions préparatoires, la question 3 aborde le cryptage, la question 4 le décryptage. 1 Cette question envisage de calculer le reste dans la divi-sion euclidienne par 55 de certaines puissances de l’entier 8 . a Vérifier que 8 7 ≡ 2 ( mod. 55) . En déduire le reste dans la division euclidienne par 55 du nombre 8 21 . b Vérifier que 8 2 ≡ 9 ( mod. 55) , puis déduire de la ques-tion a le reste dans la division euclidienne par 55 de 8 23 . 2 Dans cette question, on considère l’équation: ( E ) 23 · x − 40 · y =1 , dont les solutions sont des couples ( x ; y ) d’entiers relat-ifs. a Justifier le fait que l’équation ( E ) admet au moins un couple solution. b Donner un couple, solution particulière de l’équation ( E ) . c Déterminer tous les couples d’entiers relatifs solution de l’équation ( E ) . d En déduire qu’il existe un unique entier d vérifiant les conditions : 0 d< 40 et 23 · d ≡ 1 ( mod. 40) . 3 Cryptage dans le système RSA Une personne A choisit deux entiers premiers p et q , puis calcule les produits N = p · q et n = p − 1 q − 1 . Elle choisit également un entier naturel c premier avec n . La personne A publie le couple ( N ; c ) , qui est une clé publique permettant à quiconque de lui envoyer un nom-bre crypté. Les messages sont numérisés et transformés en une suite d’entiers compris entre 0 et n − 1 . Pour crypter un entier a de cette suite, on procède ainsi : on calcule le reste b dans la division euclidienne par N du nombre a c , et le nombre crypté est l’entier b . Dans la pratique, cette méthode est sûre si la personne A choisit des entiers premiers p et q très grands, s’écrivant avec plusieurs dizaines de chiffres. On va l’envisager ici avec des nombres plus simples : p =5 et q =11 . La personne A choisit également c =23 . a Calculer les nombres N et n , puis justifier que la valeur de c vérifie la condition voulue. b Un émetteur souhaite envoyer à la personne A le nom-bre a =8 . Déterminer la valeur du nombre crypté b . 4 Décryptage dans le système RSA La personne A calcule dans un premier temps l’unique entier naturel d vérifiant les conditions : 0 d<n et c · d ≡ 1 ( mod. n ) . Elle garde secret ce nombre d qui lui permet, à elle seule, de décrypter les nombres qui lui ont été envoyés cryptés avec sa clé publique. Pour décrypter un nombre crypté b , la personne A calcule le reste a dans la division euclidienne par N du nombre b d , et le nombre en clair - c’est-à-dire le nombre avant cryptage - est le nombre a . On admet l’existence et l’unicité de l’entier d , et le fait que le décryptage fonctionne. Les nombres choisis par A sont encore p =5 , q =11 et c =23 . a Quelle est la valeur de d ? b En appliquant la règle de décryptage, retrouver le nom-bre en clair lorsque le nombre crypté est b =17 . E.8149 Amérique du Sud 2018 https://chingmath.fr sacados/8140 sacados/8149