Université de Paris 7 2003-2004 CAPES: Ecrit

Arithmétique

Exercice I:

On s’intéresse au sous-groupe ℤ^{2} ⊂ ℝ^{2}. Deux points A, B ∈ ℝ^{2} sont dits visibles l’un de l’autre si le segment ouvert ]A, B[ ne contient aucun point de ℤ^{2} : ]A, B[ ∩ ℤ^{2} = ∅.

1) Montrer que les points A = (a, a′) ∈ ℤ^{2} visibles de l’origine sont ceux pour lesquels a et a′ sont premiers entre eux.

2) Etant donnés deux points A, B ∈ ℝ^{2} non alignés avec l’origine, montrer que le nombre det(\overrightarrow{OA}, \overrightarrow{OB}) est égal à l’aire algébrique du parallélogramme de sommets O, A, B, O + \overrightarrow{OA} + \overrightarrow{OB}. En particulier, ce nombre est un entier lorsque A, B ∈ ℤ^{2}.

3) On suppose les points A, B ∈ ℤ^{2} visibles depuis O et non alignés. Montrer que l’entier naturel |det(\overrightarrow{OA}, \overrightarrow{OB})| est égal au nombre de points de ℤ^{2} situés à l’intérieur du parallélogramme de sommets O, A, B, O + \overrightarrow{OA} + \overrightarrow{OB}.

4) Si le point A = (a, a′) ∈ ℤ^{2} est visible depuis O, décrire géométriquement les points M = (m, m′) ∈ ℤ^{2} vérifiant la relation de Bézout am′ − ma′ = ±1.

5) On appelle (i, j) la base canonique de l’espace vectoriel ℝ^{2}. Démontrer qu’il existe un point A ∈ ℕ^{∗} × ℕ^{∗} tel qu’aucun des quatre points A, A + i, A + j, A + i + j ne soit visible de l’origine.

Exercice II:

Soient a, b deux entiers, avec a ≥ b ≥ 1. On considère un rectangle de côtés a, b quadrillé en ab carrés égaux. Partant d’un coin du rectangle, on trace la bissectrice en ce coin jusqu’à ce qu’on rencontre un côté du rectangle. Si le rectangle n’est pas un carré, on continue dedans par réflexion sur ce côté, etc... Vérifier l’assertion suivante : pour que tous les petits carrés soient parcourus, il faut et il suffit que a et b soient premiers entre eux.

Exercice III:

1) Soit a un entier, a > 2. Montrer que pour n > 1, a^{n} − 1 n’est pas premier.

2) Montrer que si 2^{n} − 1 est premier, alors n est premier.

Exercice IV:

On définit pour tout n ∈ ℕ, F_{n} = 2^{2^{n}} + 1.

1) Montrer que si 2^{n} + 1 est un nombre premier, n est une puissance de 2.

2) Montrer que 5 × 2^{7} + 1 divise 5^{4} × 2^{28} − 1 et que 5^{4} + 2^{4} divise 5^{4} × 2^{28} + 2^{32}. En déduire que 641 divise F_{5}.

3) Montrer que pour tout couple (m, n) d’entiers distincts F_{n} et F_{m} sont premiers entre eux. (On pourra supposer que n > m et utiliser l’identité 2^{2^{n}} + 1 = (2^{2^{m}})^{2^{n−m}} − (−1)^{2^{n−m}} + 2.)

Exercice V:

Déterminer les entiers n vérifiant les systèmes de congruences.

1) n ≡ 3 (mod 37) et n ≡ 4 (mod 52).

2) n ≡ 21 (mod 12) et n ≡ 12 (mod 21).

3) n ≡ 2 (mod 2), n ≡ 3 (mod 3) et n ≡ 4 (mod 4).

Exercice VI:

On veut démontrer que tout entier N positif dont l’écriture en base 10 se termine par 1,3,7 ou 9 a un multiple qui ne s’écrit qu’avec des 1.

1) Vérifier la propriété pour N = 3 puis pour N = 7.

2) Ecrire un nombre qui ne s’écrit qu’avec des 1 comme la somme d’une progression géométrique.

3) Utiliser l’indicateur d’Euler pour donner une solution du problème.

4) En déduire qu’en base 10, tout entier N ∈ ℕ a un multiple qui ne s’écrit qu’avec des 1 au début et des 0 à la fin.

Exercice VII:

Soit n un entier au moins égal à 2. Montrer que (n − 1)! est congru mod n à :

a) -1 si n est premier,  b) 2 si n = 4,  c) 0 sinon.

Exercice VIII:

1) Quel est le dernier chiffre de 7777^{7777}?

2) Quels sont les restes des divisions euclidiennes de 900^{2000} et de 101^{102^{103}} par 13?

3) Quel est le reste de la division euclidienne de 31^{32^{33}} par 7?

4) Quel est le reste de la division euclidienne de 100^{100^{100}} par 12?

Exercice IX:

Résoudre les équations suivantes :

1) x^{5} ≡ 1 (mod 3)

2) x^{3} ≡ 1 (mod 7)

3) x^{4} ≡ 1 (mod 17)

4) 1 + x + ... + x^{4} ≡ 0 (mod 31)

Exercice X:

1) Résoudre l’équation x^{2} + 4x − 1 = 0 dans ℤ/11ℤ.

2) Montrer que l’équation x^{2} + 5x + 2 = 0 n’a pas de solution dans ℤ/11ℤ.

3) Résoudre l’équation x^{2} + 6x − 13 = 0 dans ℤ/21ℤ.

4) Résoudre l’équation x^{2} + 3x + 2 = 0 dans ℤ/6ℤ.

5) Résoudre l’équation x^{2} + 4x + 6 = 0 dans ℤ/9ℤ.