Untitled - Noobvoyage

ARITHMÉTIQUE DES ENTIERS RELATIFS
Christophe Bertault — Mathématiques en MPSI
1
2
DIVISIBILITÉ, DIVISION EUCLIDIENNE
ET NOMBRES PREMIERS ENTRE EUX
ET CONGRUENCES
1
Montrer que 2123 + 3121 est divisible par 11.
10
————————————–
2
Montrer que n(n + 2)(7n − 5) est divisible par 6
pour tout n ∈ Z.
11
Calculer le reste de la division euclidienne :
1) de 32189 par 25.
2) de 55970321 par 8.
4321
1234
3) de 1234
+ 4321
par 7.
Pour quelles valeurs de n ∈ Z l’entier :
2
2
12
2
n + (n + 1) + (n + 3)
Simplifier (a + b) ∧ (a ∨ b) pour tous a, b ∈ Z.
————————————–
est-il divisible par 10 ?
5
1) Calculer n4 + 3n2 − 3 ∧ (n + 1) pour tout n ∈ N.
2) Montrer que pour tout n ∈ N :
n4 + 3n2 − n + 2 ∧ n2 + n + 1 = (n − 2) ∧ 7.
————————————–
————————————–
4
ln a
est irrationnel pour tous a, b ¾ 2
ln b
premiers entre eux.
Montrer que
————————————–
————————————–
3
PGCD, PPCM
13
————————————–
¦
©
Montrer que pour tout p ∈ P \ 2, 3 :
Montrer que pour tous a, b ∈ N∗ :
Ua ∩ U b = Ua∧b .
————————————–
p2 ≡ 1 [24].
14
————————————–
6
Montrer que pour tous n ∈ N∗ et a, b ∈ Z, si
a ≡ b [n] alors : a n ≡ b n n2 .
————————————–
7
Montrer que pour tous a ∈ Z impair et n ∈ N :
n
a2 ≡ 1 2n+1 .
————————————–
8
Soient x, y, z ∈ Z.
1) Montrer que x 2 + y 2 est divisible par 7 si et seulement si x et y le sont.
2) Montrer que si x 3 + y 3 + z 3 est divisible par 7,
alors x, y ou z aussi.
15
————————————–
9
1) Montrer que n + 1 et 2n + 1 sont premiers entre
eux pour toutn ∈N.
2n
est pair pour tout n ∈ N∗ .
2) Montrer que
n

2n + 2
, que n + 1 divise
3) En déduire, grâce à
n+1

2n
pour tout n ∈ N.
n
————————————–
Soient a, b ∈ N∗ premiers entre eux.
1) Pour tout k ∈ N, on note rk le reste de la division
euclidienne de a k par b. Pourquoi l’application
k 7−→ rk n’est-elle pas injective de N dans N ?
2) En déduire que pour un certain n ∈ N∗ :
a n ≡ 1 [b].
Soit (un )n∈N une suite réelle sous-additive,
i.e. telle que pour tous m, n ∈ N : um+n ¶ um + un .
un
existe dans
On souhaite montrer que la limite lim
n→+∞ n
R ∪ − ∞ (lemme sous-additif de Fekete).
nu o
n
On pose A =
.
n n∈N∗
1) On suppose A minoré et on pose a = inf A . On
un
= a. Soit ǫ > 0.
va montrer que lim
n→+∞ n
a) Montrer que pour un certain N ∈ N∗ :
uN
ǫ
< a+ .
a¶
N
2
b) Soit n ∈ N∗ . On introduit la division euclidienne de n par N : n = N q + r avec
q ∈ N et r ∈ ¹0, N − 1º. Montrer qu’alors :
un
uN u r
¶
+ .
n
N
n
c) Conclure.
un
= −∞ dans le cas où A
2) Montrer que lim
n→+∞ n
n’est pas minoré.
————————————–
16
Pour tout n ∈ N∗ , on note div(n) l’ensemble
des diviseurs positifs de n.
Soient a, §
b ∈ N∗ premiers entre eux. Montrer que l’apdiv(a) × div(b) −→ N
plication
est bijective de
(k, l)
7−→ kl
div(a) × div(b) sur div(a b).
————————————–
17
Soient a1 , . . . , a r ∈ N∗ premiers entre eux
deux à deux et b ∈ Z.
Y
ai , k décrivant ¹1, rº,
1) Montrer que les entiers
1¶i¶r
i6=k
sont premiers entre eux dans leur ensemble.
2) En déduire qu’il existe une et une seule famille
d’entiers ( y, x 1 , . . . , x r ) telle que :
r
X
xk
b
= y+
a1 . . . a r
a
k=1 k
avec 0 ¶ x i < ai pour tout i ∈ ¹1, rº.
————————————–
1
ARITHMÉTIQUE DES ENTIERS RELATIFS
Christophe Bertault — Mathématiques en MPSI
4
————————————–
18
On dira qu’une partie non vide E de N∗ est sympathique
x+y
si pour tous x, y ∈ E :
∈ E.
x∧y
Montrer
1)
que toute partie sympathique contient
2 et que 2 est une partie sympathique.
Déterminer toutes les parties sympathiques
2)
qui contiennent 1.
3)
Soit E une partie sympathique non réduite à 2 et ne contenant pas 1.
On pose m = min E \ 2 .
a) Montrer que m est impair.
b) Montrer que E contient tous les entiers impairs plus grands que m.
c) Montrer que E contient 2N∗ .
d) En déduire E.
25
19
Pour tous entiers a ¾ 2 et n ¾ 2, montrer que
si a n − 1 est premier, alors a = 2 et n est premier.
Pour tout p ¾ 2, l’entier M p = 2 p − 1 est appelé le
pème nombre de Mersenne. Tous ne sont pas premiers,
par exemple M11 = 23 × 89.
26
VALUATIONS p-ADIQUES
Soit n ∈ N∗ . Montrer que si n est à la fois un
carré parfait et un cube parfait, alors il est la puissance
sixième d’un entier.
Factoriser a2n+1 + b2n+1 par a + b pour
tous n ∈ N et a, b ∈ C.
b) Pour tout n ∈ N∗ , montrer que si 2n + 1 est
premier, alors n est une puissance de 2.
n
Pour tout n ∈ N, l’entier Fn = 22 + 1 est appelé le nème
nombre de Fermat. On peut vérifier que F0 , F1 , F2 , F3 , F4
sont premiers et on conjecture que ce sont là les seuls
nombres de Fermat premiers. Les nombres de Fermat
premiers jouent un rôle étonnant dans le problème de
la constructibilité à la règle et au compas des polygones
réguliers.
2) a) Montrer que pour tout n ∈ N :
1) a)
Fn+1 = F0 F1 . . . Fn + 2.
b) En déduire que Fm et Fn sont premiers entre
eux pour tous m, n ∈ N distincts.
————————————–
20
Soient a, b ∈ N et k ¾ 2 entier. Si a et b sont premiers entre eux et si a b est la puissance kème d’un entier, montrer que a et b sont eux-mêmes des puissances
kèmes d’entiers.
————————————–
27
1) a) Montrer que tout entier naturel congru à 3
modulo 4 possède au moins un diviseur premier congru à 3 modulo 4.
b) Montrer qu’il existe une infinité de nombres
premiers congrus à 3 modulo 4.
2) Montrer qu’il existe une infinité de nombres premiers congrus à 5 modulo 6.
————————————–
21
Soient a, b ∈ N∗ . Montrer que si a2 divise b2 , alors
a divise b.
————————————–
22
Montrer que pour tous a, b, n ∈ N∗ :
n
n
————————————–
n
(a ∧ b) = a ∧ b .
Soit p ∈ P.
1) Montrer que :
28
————————————–
23
∀ y ∈ ¹1, p−1º,
1) Montrer que pour tous p ∈ P et n ∈ N :
vp n! =
+∞
X
k=1
n
pk

PREMIERS
————————————–
————————————–
3
NOMBRES
∃ ! x ∈ ¹1, p−1º/
x y ≡ 1 [p].
2) En déduire le théorème de Wilson :
(p − 1)! ≡ −1 [p].
(formule de Legendre),
3) On suppose p impair. Montrer que :

p+1
p−1 2
! ≡ (−1) 2 [p].
2
où la somme
est faussement infinie car pour tout
n
∗
= 0 dès que p k > n.
k∈N ,
pk
2) Par combien de zéros l’entier 100! s’achève-t-il ?
————————————–
————————————–
5
Déterminer tous les entiers n ∈ N∗ pour les24
n
quels 2 divise 3n − 1.
29
————————————–
2
ÉQUATIONS
DIOPHANTIENNES
Résoudre les équations suivantes d’inconnue
(x, y) ∈ N§2 :
x∧y=3
1)
x + y = 21.
2)
(x ∧ y) + (x ∨ y) = 2x + 3 y.
ARITHMÉTIQUE DES ENTIERS RELATIFS
Christophe Bertault — Mathématiques en MPSI
3)
x ∨ y = x + y − 1.
37
Résoudre l’équation y 3 = x 2 + x d’inconnue
(x, y) ∈ Z .
2
————————————–
————————————–
Résoudre les équations suivantes d’inconnue (x, y) ∈ Z2 :
30
9x 2 − y 2 = 32.
1)
2)
x 2 − 2 y 2 = 3 en raisonnant modulo 8.
15x 2 − 7 y 2 = 9 en raisonnant mo3)
dulo 3.
38
————————————–
31
Soient a, b ∈ Z et n ∈ N∗ . On s’intéresse à
l’équation : a x ≡ b [n] Æ d’inconnue x ∈ Z.
1) Montrer que Æ n’a pas de solution si b n’est pas
un multiple de a ∧ n.
2) On suppose à présent que a ∧ n divise b.
a) Montrer, grâce à une relation de Bézout de a
et n, que Æ possède une solution x 0 .
b) Résoudre alors Æ.
3) Résoudre l’équation 7x ≡ 3 [17] d’inconnue x ∈ Z.
————————————–
39
Soient a, b, c ∈ Z, (a, b) 6= (0, 0). On s’intéresse à l’équation : a x + b y = c Æ d’inconnue
(x, y) ∈ Z2 .
1) Montrer que Æ n’a pas de solution si c n’est pas
un multiple de a ∧ b.
2) On suppose à présent que a ∧ b divise c.
a) Montrer, grâce à une relation de Bézout de a
et b, que Æ possède une solution (x 0 , y0 ).
b) Résoudre alors Æ.
3) Résoudre les équations d’inconnue (x, y) ∈ Z2 :
a)
7x − 12 y = 3.
b) 20x − 53 y = 3.
————————————–
§
x ≡ 1 mod 5
Résoudre le système
d’inx ≡ 2 mod 11
33
connue x ∈ Z.
————————————–
34
On veut résoudre l’équation : x 2 + y 2 = 3z 2
Æ d’inconnue (x, y, z) ∈ N3 .
1) En raisonnant modulo 4, montrer que pour toute
solution (x, y, z) de Æ, x, y et z sont pairs.
2) En déduire les solutions d’Æ.
————————————–
35
On veut résoudre l’équation x y = y x d’inconnue (x, y) ∈ N∗ .
1) Soient x, y ∈ N∗ . On suppose que x ¶ y et que
x y = y x . Montrer que x divise y en étudiant
leur PGCD.
2) Conclure.
————————————–
36
On veut montrer que l’équation 2n + 1 = m3 d’inconnue (m, n) ∈ N2 n’a pas de solution. On suppose par
l’absurde qu’elle en possède une (m, n).
Montrer que m − 1 et m2 + m + 1 sont des
1)
puissances de 2.
2)
Conclure.
————————————–
————————————–
32
On veut montrer que l’équation y 2 = x 3 + 7
d’inconnue (x, y) ∈ Z2 n’a pas de solution. On suppose
par l’absurde qu’elle en possède une (x, y).
Montrer que x est impair.
1)
2) Factoriser x 3 + 8. En déduire que y 2 + 1 possède
un facteur premier p congru à 3 modulo 4.
3) Etudier y p−1 de deux façons différentes et conclure.
Soit p ∈ P. Résoudre l’équation x 2 + px = y 2
d’inconnue (x, y) ∈ N2 .
————————————–
3

Download Report