Congruences (Term S spécialité)

Fiches récapitulatives et rappels de cours.
Avatar de l’utilisateur
Job
Propriétaire du forum
Messages : 2584
Inscription : 28 juin 2013, 15:07
Contact :

Congruences (Term S spécialité)

Message par Job » 11 novembre 2013, 14:44

Définition

$n$ est un entier naturel supérieur ou égal à 2, $a$ et ^b^sont des entiers relatifs. On dit que $a$ est congru à $b$ modulo $n$ lorsque dans les divisions euclidiennes de $a$ et $b$ par $n$ le reste est le même.

Propriétés élémentaires

$a\equiv b\ [n]$ équivaut à $n$ divise $a-b$

$a \equiv 0\ [n]$ équivaut à $n$ divise $a$.

Tout entier relatif $a$ est congru, modulo $n$, à un unique entier naturel $r$ tel que $0\leq r \leq n-1$

Congruences et opérations

$a$, $b$, $a'$, $b'$ étant des entiers relatifs tel que $a\equiv a'\ [n]$ et $b\equiv b'\ [n]$ alors

$a+b\equiv a'+b'\ [n]$ (prop 1)

$ab\equiv a'b'\ [n]$ (prop 2)

Pour tout entier $k$, $ka\equiv ka'\ [n]$ (prop 3)

Pour tout entier naturel $p$ non nul $a^p\equiv a'^p\ [n]$ (prop 4)

Exemples d'exercices

1) Un grand classique

1) Pour tout entier relatif $x$ montrer que $x^2\equiv 0\ [4]$ ou $x^2 \equiv 1\ [4]$

2) Montrer que, quel que soit les entiers relatifs $x$ et $y$, $x^2+y^2$ n'est jamais congru à 3 modulo 4

3) Que peut-on en déduire si un entier naturel $a$ est congru à 3 modulo 4 ?

Solution

1) Dans la division par 4, le reste appartient à {0, 1, 2, 3}

En utilisant la propriété 4 :
Si le reste est 0, $x\equiv 0\ [4]$ donc $x^2\equiv 0\ [4]$
Si le reste est 1, $x\equiv 1\ [4]$ donc $x^2\equiv 1\ [4]$
Si le reste est 2, $x\equiv 2\ [4]$ donc $x^2\equiv 4 \equiv 0\ [4]$
Si le reste est 3, $x\equiv 3\ [4]$ donc $x^2\equiv 9\ [4] \equiv 1\ [4]$

2) On utilise la propriété 1
Si $x^2\equiv 0\ [4]$ et $y^2\equiv 0\ [4]$ alors $x^2+y^2 \equiv 0\ [4]$
Si $x^2\equiv 1\ [4]$ et $y^2\equiv 0\ [4]$ alors $x^2+y^2 \equiv 1\ [4]$
Si $x^2\equiv 0\ [4]$ et $y^2\equiv 1\ [4]$ alors $x^2+y^2 \equiv 1\ [4]$
Si $x^2\equiv 1\ [4]$ et $y^2\equiv 1\ [4]$ alors $x^2+y^2 \equiv 2 [4]$

3) D'après la question précédente, si un nombre est congru à 3 modulo 4, il ne peut jamais être écrit sous la forme d'une somme de 2 carrés.

2) Détermination du reste, dans la division euclidienne d'un très grand nombre par un entier naturel

Quel est le reste, dans la division euclidienne par 13 de $2010^{2013}$

Solution

On fait la division euclidienne de 2010 par 13. Le reste est 8 donc $2010 \equiv 8\ [13]$
En utilisant la propriété 4, $2010^{2013} \equiv 8^{2013}\ [13]$

$8^2=64$ donc $8^2\equiv 12 \equiv (-1)\ [13]$

$2013 = 1006\times 2 +1$ donc $8^{2013}=(8^2)^{1006}\times 8$

En utilisant les propriétés 2 et 4 on a alors $8^{2013}\equiv (8^2)^{1006} \times 8 \equiv (-1)^{1006}\times 8 \equiv 1\times 8\ [13]$

Le reste cherché est donc 8

Répondre