Congruences dans Z - Modulo [n] - Problèmes

On considère l'équation $(E)$ : $x^2 - 7y^2 = 3$ où $x$ et $y$ sont deux entiers relatifs.

1. Justifier que si le couple d'entiers $(x~;~y)$ est solution alors $x^2 \equiv 3 \, [7]$.
2. Déterminer les restes possibles de la division de $x^2$ par $7$.
3. En déduire que l'équation $(E)$ n'a pas de solution.

On considère l'équation (E) : $17x^2-31y^2 = 22$ où $x$ et $y$ sont des entiers relatifs.
Montrer en utilisant les congruences modulo 8 , que l'équation (E) n'a pas de solution.

On considère un entier naturel $a$ défini par son écriture décimale $a = \overline{a_n a_{n-1}\cdots a_0}$ avec $a_n \neq 0$.
On a donc : \[a=a_n \times 10^n + a_{n-1} \times 10^{n-1} + \cdots + a_1 \times 10 + a_0 \]

1. Montrer que l'entier $a$ est divisible par $3$ si et seulement si la somme de ses chiffres est divisible par $3$.
2. Montrer de même que l'entier $a$ est divisible par $9$ si et seulement si la somme de ses chiffres est divisible par $9$.
3. $983652145784512369566$ est-il divisible par $3$ ? Par $9$ ?

On considère un entier naturel $a$ défini par son écriture décimale $a=\overline{a_na_{n-1}...a_1a_0}$ avec $a_n\ne 0$.
On a donc: $a=a_n\times 10^n+a_{n-1}\times 10^{n-1}+...+a_1\times 10^1+a_0$. Le rang du chiffre $a_k$ est $k$.

1. Démontrer qu'un entier est divisible par 11 si, et seulement si la somme de ses chiffres de rang pair moins la somme de ses chiffres de rang impair est divisible par 11.
2. L'entier 619 852 805 est-il divisible par 11?

On admet le critère de divisibilité par $7$ suivant :
Un entier est divisible par $7$ si et seulement si la différence entre son nombre de dizaines et le double de son chiffre des unités l'est.

1. A l'aide de ce critère, déterminer si $4361$ est divisible par $7$. Même question avec $542$.
2. Démontrer ce critère.

Pour coder un message, on peut procéder de la façon suivante : chaque lettre du message munie de son numéro d'ordre $n$ (voir tableau ci-dessous) est remplacée par la lettre de l'alphabet munie du numéro d'ordre $p$ ($0 \leqslant p \leqslant 25$ ) obtenu à l'aide de la formule $p \equiv 3 n + 7 \, [26]$.

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

1. Vérifier qu'avec ce chiffrement le S est remplacé par le J.
2. Coder le mot SECRET.
3. Montrer que si $p \equiv 3n + 7 \, [26]$ alors $n \equiv 9p +15 \, [26]$.
4. Déchiffrer le message suivant : KGHSX

On considère la suite numérique $(u_n)$ définie par $u_0=14$ et pour tout entier naturel $n$, $u_{n+1} = 5u_n-6$.

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. 1. Montrer que pour tout entier $n$, $u_{n+2}\equiv u_n \, [4]$.
      En déduire que, pour tout entier naturel $k$, $u_{2k+1}\equiv 0 \,[4]$ et $u_{2k}\equiv 2 \,[4]$.
   2. Montrer par récurrence que, pour tout entier naturel $n$, $2u_n=5^{n+2}+3$.
   3. Montrer que, pour tout entier naturel $n$, $5^{n+2}\equiv 25 \,[100]$.
   4. En déduire que, pour tout entier naturel $n$, $2u_n \equiv 28 \,[100]$.
      Déterminer les deux derniers chiffres dans l'écriture décimale de $u_n$.

On appelle nombres de Fermat les entiers $F_n = 2^{2^n}+1$ avec $n$ un entier naturel.

1. 1. Calculer $F_0$, $F_1$, $F_2$, $F_3$ et $F_4$. Que remarque-t-on ?
   2. En 1640, Pierre de Fermat annonce qu'il est persuadé que les nombres $F_n$ sont premiers.
      A l'aide de la calculatrice, vérifier que $641$ divise $F_5$. Quelle question peut-on se poser ?
2. 1. Montrer que pour tout entier naturel $n$, $F_{n+1} = (F_n -1)^2 +1$.
   2. En déduire par un raisonnement par récurrence que pour $n \geqslant 2$, l'écriture décimale de $F_n$ se termine par un $7$.

1. Compléter la table des restes modulo 5 ci-dessous:
   

   $x\equiv $	0	1	2	3	4
   $x^2\equiv $

2. En déduire qu'un triangle rectangle qui a tous ses côtés entiers, en a au moins un qui est divisible par 5.

Un rép-unit est un entier naturel dont l'écriture décimale ne comprend que le chiffre $1$ comme par exemple $11$ ou encore $111 111$. Le but de cet exercice est de trouver tous les répunits qui sont des carrés parfaits.

1. Soit $n$ un entier naturel. On suppose que l'écriture décimale de $n^2$ se termine par le chiffre $1$.
   1. Quel peut être le chiffre des unités de $n$ ?
   2. En remarquant qu'un entier se terminant par $1$ ou $9$ peut s'écrire $10k + 1$ ou $10k-1$ avec $k$ entier, montrer que $n^2 \equiv 1 \, [20]$.
2. En déduire tous les rép-units qui sont des carrés parfaits.

Montrer sans utiliser de calculatrice et à l'aide des congruences, que 1295377 n'est pas un carré parfait.

1. Déterminer le reste de $2^{2012}$ dans la division euclidienne par 5.
2. En déduire le chiffre des unités de $2^{2012}$.

Démontrer l'équivalence entre les deux propriétés $\rm P_1$ et $\rm P_2$ suivantes, pour $a$ entier relatif :

• $\rm P_1$ : L'équation d'inconnue $x$, $ax\equiv 1~[6]$ n'a aucune solution dans $\mathbb{Z}$
• $\rm P_2$ : $a$ est divisible par 2 ou par 3.