Arithmétique dans Z

POIRET Aurélien
TD no 16
1
Arithmétique dans Z
20142015
MPSI
Résolution d'équations diophantiennes
Exercice No 1 :
Résoudre dans Z les équations suivantes :
1. x − 1 | x + 3.
2. x + 2 | x2 + 2.
Exercice No 2 :
Résoudre dans Z2 les équations suivantes :
1. xy = 3x + 2y .
2. x1 + y1 = 15 .
3. x2 − y 2 − 4x − 2y = 5.
Exercice No 3 :
Trouver les entiers n ∈ Z tel que 10 | n2 + (n + 1)2 + (n + 3)2 .
Exercice No 4 :
Soient d, m ∈ N. Donner une condition nécessaire et susante pour que le système
(
pgcd(x, y) = d
ppcm(x, y) = m
possède un couple (x, y) ∈ N2 solution.
Exercice No 5 :
Résoudre dans N2 l'équation :
pgcd(x, y) + ppcm(x, y) = x + y.
Exercice No 6 :
pgcd(x, y) = 5
.
ppcm(x, y) = 60
(
x + y = 100
1.
2.
2
Résoudre dans N2 les systèmes :
(
pgcd(x, y) = 10
.
Division euclidienne
Exercice No 7 :
b.
Soient a ∈ Z et b ∈ N? , on note q le quotient de la division euclidienne de a − 1 par
Déterminer, pour tout n ∈ N, le quotient de la division euclidienne de (abn − 1) par bn+1 .
Exercice No 8 :
Quel est le reste de la division euclidienne de 12344321 + 43211234 par 7 ?
Exercice No 9 :
1
1. Montrer que si r est le reste de la division euclidienne de a ∈ N par b ∈ N? alors 2r − 1 est le
reste de la division euclidienne de 2a − 1 par 2b − 1.
2. Montrer que pgcd(2a − 1, 2b − 1) = 2pgcd(a,b) − 1.
3
Pgcd et ppcm
Exercice No 10 :
Déterminer le pgcd et les coecients de l'égalité de Bézout des entiers a et b
suivants :
1. a = 33 et b = 24.
2. a = 37 et b = 27.
3. a = 270 et b = 105.
Exercice No 11 :
Soient a, b, d ∈ Z. Montrer l'équivalence
(∃u, v ∈ Z / au + bv = d) ⇔ pgcd(a, b) | d.
Exercice No 12 :
Soient a et b premiers entre eux.
Montrer que a ∧ (a + b) = b ∧ (a + b) = 1 puis que (a + b) ∧ ab = 1.
Exercice No 13 :
Soient a, b ∈ Z.
1. On suppose a ∧ b = 1. Montrer que (a + b) ∧ ab = 1.
2. On revient au cas général. Calculer pgcd(a + b, ppcm(a, b)).
Exercice No 14 :
4
Soient a et b premiers entre eux et c ∈ Z. Montrer que pgcd(a, bc) = pgcd(a, c).
Nombres premiers entre-eux
Exercice No 15 :
Montrer que, pour tout n ∈ N? ,
1. (n2 + n) ∧ (2n + 1) = 1.
2. (3n2 + 2n) ∧ (n + 1) = 1.
Exercice No 16 :
Montrer !
que, pour tout entier n ∈ N? , n + 1 et 2n + 1 sont premiers entre eux.
En déduire que n + 1 |
Exercice No 17 :
2n
n
.
Soit n ∈ N. Montrer que les entiers
ai = i.n! + 1
pour i ∈ {1, . . . , n + 1} sont deux à deux premiers entre eux.
Exercice No 18 :
pose
Soit U1 , · · · Un n entiers premiers entre-eux deux à deux. Pour i ∈ {1, · · · n}, on
Ubi =
n
Y
j=1
j6=i
2
Uj .
c1 , · · · , U
cn sont premiers entre-eux dans leur ensemble.
Montrer que les entiers U
Exercice No 19 :
Soit n ∈ N, montrer
√
En déduire que
5
√
2∈
/ Q et
√
n ∈ Q ⇔ ∃m ∈ N / n = m2 .
3∈
/ Q.
Nombres premiers et théorème de la décomposition primaire
Exercice No 20 :
Montrer que les nombres suivants sont composés, c'est-à-dire non premier,
1.
+
+ 4n + 1 avec n ∈ N? .
2. n4 − n2 + 16 avec n ∈ Z.
4n3
6n2
Exercice No 21 : Soient a et p deux entiers supérieurs à 2.
Montrer que si ap − 1 est premier alors a = 2 et p est premier.
Exercice No 22 :
Soit p > 3 un nombre premier. Montrer que 24 | p2 − 1.
Exercice No 23 :
Soit E = {4k − 1 / k ∈ N? }.
1. Montrer que pour tout n ∈ E , il existe p ∈ P ∩ E tel que p | n.
2. En déduire qu'il y a une innité de nombre premier p tel que p ≡ −1
[4].
Exercice No 24 :
On note div(n) l'ensemble des diviseurs positifs d'un entier n ∈ Z.
1. Montrer que si (a, b) ∈ Z2 sont premiers entre eux alors l'application ϕ : div(a)×div(b) → div(ab)
dénie par ϕ(k, `) = k` est une bijection.
2. Soient p ∈ P et α ∈ N? . Déterminer les diviseurs positifs de pα .
3. Soit n ∈ N\ {0, 1} et n =
N
Q
k=1
pαk k sa décomposition primaire.
Quel est le nombre de diviseurs positifs de n ?
Exercice No 25 :
1.
2.
3.
4.
6
Soit σ : Z → N qui à n ∈ Z associe la somme de diviseurs positifs de n.
Soit p ∈ P et α ∈ N? . Calculer σ(pα ).
Soient a, b ∈ Z premiers entre eux.
Montrer que tout diviseur positif d du produit ab s'écrit de manière unique d = d1 d2 avec d1 et
d2 diviseurs positifs de a et b.
En déduire que si a et b sont premiers entre eux alors σ(ab) = σ(a)σ(b).
Exprimer σ(n) en fonction de la décomposition primaire de n.
Valuation
Exercice No 26 :
p-adique
Soient a et b premiers entre eux et c ∈ Z. Montrer que pgcd(a, bc) = pgcd(a, c).
Exercice No 27 :
Soient a et b des entiers relatifs tels que an+1 divise bn pour un entier naturel n
non nul. Montrer que a divise b.
3
Exercice No 28 :
Soient a et b des entiers relatifs tels que a2 divise b2 . Montrer que a divise b.
Exercice No 29 :
Pour p ∈ P et n ∈ Z, on note vp (n) l'exposant de la plus grande puissance de p
divisant n.
1. Montrer que v2 (1000!) = 994.
2. Plus généralement, calculer vp (n!). j
k
Indication : On rappelle que
Exercice No 30 :
7
∀x ∈ R,
bpxc
p
= bxc.
Calculer, pour p premier et k ∈ {0, · · · , p}, vp
p
k
.
Calcul en congruence
Exercice No 31 :
Montrer que 11 | 2123 + 3121 .
Exercice No 32 :
Montrer que pour tout n ∈ N :
a) 6 | 5n3 + n
d) 11 | 38n × 54 + 56n × 73
b) 7 | 32n+1 + 2n+2
e) 9 | 4n − 1 − 3n
Exercice No 33 :
Montrer
Exercice No 34 :
Montrer que si n est entier impair alors
7 | x et 7 | y ⇔ 7 | x2 + y 2 .
n2 ≡ 1
Exercice No 35 :
[m] ⇔ λa ≡ λb
[m] .
Résoudre le système
(
Exercice No 37 :
[8] .
Soient λ, a, b ∈ Z et m ∈ N? . On suppose λ et m premiers entre eux. Montrer
a≡b
Exercice No 36 :
c) 5 | 22n+1 + 32n+1
f) 152 | 16n − 1 − 15n
x≡2
[10]
x≡5
[13]
.
Soit q un nombre impair. Montrer que, pour tout n ∈ N? ,
n
X
n(n + 1)
divise
kq .
2
k=1
4
8
Sous-groupes de
(R, +)
et
(R?+ , ×)
Exercice No 38 : Description des sous-groupes additifs de
R
On xe G un sous-groupe non-réduit à {0} de (R, +).
1. Montrer que l'ensemble G ∩ R?+ possède une borne inférieure que l'on note a.
2. On suppose que a ∈ G ∩ R?+ . Montrer que G = aZ.
3. On suppose que a ∈
/ G ∩ R?+ . Montrer que a = 0 puis que G est dense dans R.
Exercice No 39 :
Décrire les sous-groupes de (R? , ×).
Exercice No 40 :
Soient f une fonction continue de R dans C et A une partie dense de R.
1. Montrer que f (A) est une partie dense de f (R).
2. En déduire que l'ensemble
{e2iπnx / n ∈ Z}
est dense dans le cercle trigonométrique si, et seulement si, x est irrationnel.
On rappelle que les sous-groupes additifs de
R
sont denses ou monogènes.
5

Download Report