Congruences

Parcours 1 : exercices

61

 ;

65

 ;

79

 ;

80

 ;

99

et

108

Parcours 2 : exercices

63

 ;

67

 ;

84

 ;

89

 ;

102

  et

117

Parcours 3 : exercices

66

 ;

74

 ;

90

;

105

et

112

Sans calculatrice, compléter les égalités.

[ Calculer. ]
1. Justifier que tout entier $n$ est congru modulo $7$ à $-3$ ; $-2$ ; $-1$ ; $0$ ; $1$ ; $2$ ou $3$.

2. En déduire les restes possibles de $n^2$ dans la division euclidienne par $7$.

3. Quels sont les restes possibles de $n^4$ dans la division euclidienne par $7$ ?

[ Raisonner. ]
Soit $n$ un entier naturel.

1. Démontrer par récurrence que
${\mathrm{S}}_n=0^2+1^2+2^2+3^2+\dots +n^2$$=\frac{n(n+1)(2n+1)}{6}$.

2. Quelle condition $n$ doit-il vérifier pour que $\text{S}$ soit pair ? Justifier.

[ Chercher. ]
1. Montrer que $\text{A}=2305^{2019}+1106^{2019}$ est divisible par $9$.

2. Montrer que, pour tout $n\in \mathbb{N}$, $\mathrm{B}=5^n\times 12-12^n\times 5$ est divisible par $7$.

[ Chercher. ]
1. Déterminer, suivant les valeurs de l'entier naturel non nul $n$, le reste dans la division euclidienne de $3^n$ par $5$.

2. En déduire le reste de la division euclidienne de $243^{942}$ par $5$.

[ Chercher. ]
1. Quels sont les restes possibles de la division euclidienne de $5^n$ par $6$ ?

2. En déduire le reste de la division euclidienne de $15365^{221}$ par $6$.

[ Chercher. ]
1. Quel est le chiffre des unités de $9^{231}$ ? Justifier.

2. Quel est le chiffre des unités de $4^{125}$ ? Justifier.

[ Calculer. ]
Soit $n$ est un entier naturel non nul. On pose :
1. Calculer ${\text{U}}_1$, ${\text{U}}_2$ et ${\text{U}}_3$.

2. En remarquant que $3\equiv -8[11]$, démontrer que $3^{n+3}\equiv (-1{)}^{n+1}\times 2^{3n+9}[11]$.

3. a. Démontrer que ${\text{U}}_n\equiv (-1{)}^{n+1}\times 2^{3n+9}-2^{8n+4}[11]$.

b. En déduire que ${\mathrm{U}}_n\equiv 2^{3n+9}\left((-1{)}^{n+1}-2^{5(n-1)}\right)[11]$.

4. Déterminer le reste de $2^5$ dans la division euclidienne par $11$. En déduire que $2^{5(n-1)}\equiv (-1{)}^{n-1}[11]$.

5. Déduire des questions précédentes que ${\text{U}}_n$ est divisible par $11$.

[ Raisonner. ]
Critère de divisibilité par $3$

1. Soit $\overline{abc}$ un entier naturel écrit en base $10$, c'est‑à‑dire $\overline{abc}=a\times 10^2+b\times 10+c$.
a. Démontrer que $\overline{abc}\equiv a+b+c[3]$.

b. Donner une condition nécessaire et suffisante de divisibilité par $3$ de $\overline{abc}$.

2. Généralisation : Soit $\text{A}$ un entier naturel.
On note $a_0$ ; … ; $a_n$ les entiers compris entre $0$ et $9$, $a_n\ne 0$, tels que $\mathrm{A}=\overline{a_n{a}_{n-1}{a}_{n-2}\dots a_1{a}_0}$ en base $10$.
a. Exprimer l'entier $\text{A}$ en fonction de $a_0$ ; … ; $a_n$ et des puissances de $10$.

b. Déterminer les restes possibles dans la division euclidienne de $10^n$ par $3$.

c. En déduire une condition nécessaire et suffisante de divisibilité par $3$.

[ Représenter, Modéliser. ]
1. Soit $x$ un entier relatif. Démontrer la proposition : « $x$ impair $\iff x^2\equiv 1[8]$. »

2. Résoudre dans ${\mathbb{Z}}^2$ l'équation $x^2=8y+1$.

3. En déduire l'ensemble des points à coordonnées entières de la parabole d'équation $y=\frac{1}{8}{x}^2-\frac{1}{8}$.

4. Le programme ci-dessous permet d'obtenir les coordonnées des points à coordonnées entières d'une fonction du second degré quelconque pour une abscisse comprise entre $1$ et $n$.

from math import *

def f(a, b, c, x):
  return a*x**2 + b*x + c

def coord_entieres(a, b, c, n):
  for i in range(1, n + 1):
    if f(a, b, c, i) == floor(f(a, b, c, i)):
      print([ i, f(a,b,c,i)])

Comment modifier ce programme pour qu'il donne tous les points à coordonnées entières d'abscisses comprises entre $-n$ et $n$ ?

[ Communiquer. ]
Une association culturelle affecte à chacun de ses membres un numéro d'adhérent lors de son inscription. Ce numéro comporte 7 chiffres et s'écrit donc $c_0$ $c_1$ $c_2$ $c_3$ $c_4$ $c_5$ $c_6$. Le premier chiffre $c_o$ correspond à l'activité de l'adhérent :

• $1$ pour un adhérent suivant l'activité « Informatique » ;
• $2$ pour un adhérent suivant l'activité « Travaux artistiques » ;
• $3$ pour un adhérent suivant l'activité « Lecture ».

Les deux chiffres $c_1$ et $c_2$ du numéro d'adhérent correspondent à son année de naissance (par exemple, $91$ pour un adhérent né en 1991 et $02$ pour un adhérent né en 2002).
Les trois chiffres suivants sont donnés lors de l'adhésion à l'association.
Le dernier chiffre est appelé clé de contrôle. Il est calculé automatiquement de la manière suivante : on calcule la somme $s=c_0+c_1+2c_2+3\left(c_3+c_4+c_5\right)$ ; on effectue ensuite la division euclidienne de $s$ par $9$ ; le reste obtenu est la clé de contrôle.
1. a. Le numéro $1024578$ peut‑il être le numéro d'un adhérent ? Justifier.

b. Le numéro $2923517$ peut‑il être le numéro d'un adhérent ? Justifier.

2. Un adhérent né en 1982 et inscrit à l'activité « Travaux artistiques », se voit attribuer par l'association lors de son inscription le numéro $123$.
Déterminer la clé de contrôle.

3. Lors de la saisie d'un numéro d'adhérent, une erreur est commise sur le chiffre correspondant à l'activité de l'adhérent. Cette erreur peut‑elle être détectée par la clé de contrôle ?

4. Lors de la saisie de son numéro, un adhérent intervertit les chiffres de son année de naissance. Cette erreur peut‑elle être détectée par la clé de contrôle ?

[ Calculer. ]
D'après bac S, Métropole, juin 2009
Les deux questions de cet exercice sont indépendantes.

1. a. Démontrer que, pour tout nombre entier naturel $k$, on a $2^{3k}\equiv 1[7]$.

b. Quel est le reste dans la division euclidienne de $2^{2009}$ par $7$  ?

2. Soient $a$ et $b$ deux nombres entiers naturels inférieurs ou égaux à $9$ avec $a\ne 0$.
On considère le nombre $\mathrm{N}=a\times 10^3+b$. On se propose de déterminer parmi ces nombres entiers naturels $\text{N}$ ceux qui sont divisibles par $7$.
a. Vérifier que $10^3\equiv -1[7]$.

b. En déduire tous les nombres entiers $\text{N}$ cherchés.

[ Raisonner, Modéliser. ]
Suite et congruence
On considère la suite $({\text{U}}_n)$ définie, pour tout entier naturel $n$, par ${\mathrm{U}}_n=2^n+2^{2n}+2^{3n}$.

1. Calculer ${\text{U}}_0$, ${\text{U}}_1$ et ${\text{U}}_2$.

2. Démontrer que, pour tout $n\in \mathbb{N}$, ${\mathrm{U}}_{n+3}\equiv {\mathrm{U}}_n[7]$.

3. En déduire les valeurs de $n$ pour lesquelles ${\text{U}}_n$ est divisible par $7$.

4. Recopier et compléter la fonction Python donnée ci-dessous afin qu'elle affiche les indices $i$ des termes de la suite vérifiant ${\mathrm{U}}_i\equiv 0[7]$.

from math import*
def indice(n):
	...
	for i in range(n+1):
		u = ...
		if u ... 7 == 0:
			l.append(...)
	return l