ARITHMETQUE

7° séries
2022-23

Douae Elhaouiti
 7° Douae Elhaouiti
Ex1 (nombre de Fermat) e) on suppose que p < q ; on considere q’ le quotient la
division de q par p ; Deduire : pq+q’ / a !
𝑛
Soit (Fn)n∈ℕ le nombre de Fermat définie par Fn=22 +1

1. Calculer Fn+1 - 2 en fonction de Fk avec k ∈⟦ 0,n ⟧ Ex3 (les 4k+1-nombre premier)

2. Déduire Fm ^ Fn pour tout n et m distincts
Soit X l'ensemble des nombres premiers de la forme 4k + 3 avec
k ∈ ℕ.
Ex2 (formule de Legendre)
1. Montrer que X est non vide.
∞
𝑎 2. Montrer que le produit de deux nombres de la forme
(demonstration de vp(a!)=∑ 𝐸 ( 𝑛) )
𝑝
𝑛=1 4k + 1 est encore de cette forme.
1. Soient p un nombre premier et a ∈ ℕ *\{1} 3. On suppose que X = {p1,p2, . . . , pn} et on pose
a) montrer que ∀ (x,y) ∈ N* 2 p ^ x=1 et p ^ y=1 ⇒p^xy=1 a= 4.∏𝑛𝑘=1 𝑝k -1
b) supposons que p > a montrer que : p ^ a ! = 1 a) Montrer que a admet un diviseur premier de la
c) deduire que p ∈ D(a!) ⇒ p ⩽ a forme 4k + 3
2. supposons que p ⩽ a b) Deduire que X est infinie
a) soit q le quotient de la division de a par p Monter que
∀ k∈⟦1,q⟧ ; kp divise a! Ex4 (division euclidienne)
𝑞
b) soit λ = ∏𝑘=1 𝑘𝑝 verifier que λ=q ! . pq
c) soient A={x ; x ∈ ⟦1 , a⟧ } et B ={ kp / k ∈ ⟦ 1,q ⟧ } Soient (a ,b) ∈ ℕ* × Z , considerons les nombres definient par
monter que An := b-na avec n ∈ Z
B ⊂ A et deduire que λ /a! et que pq / a!
1. Calculer pour tout n An+1 – An
d) soit E(p,a) ={ m ∈ ℕ ; pm /a !} on supp que p > q
2. On suppose que An ∉ ⟦0, a⟦ pour tout n ∈ ℕ
montrer que : SUP(E(p,a)) = q

1
 7° Douae Elhaouiti
a) Justifier l’existance de min de l’ensemble 3. Un nombre determine par 7
{n є ℕ : An ≥ a } (on le note An0 ) Soit d =10a +7
𝑛−𝑢
b) Montere que An0 + 1 < 0 , deduire une contradiction Montrer que n divisible par d Ssi + (7a+5) .u est l’aussi
10
3. Deduire l’existance du couple (q,r) qui verifier b=qa+r 4. Un nombre determine par 9
avec q un entier et r ∈ ⟦0, a⟦ Soit d=10a+9 avec
4. Montrer par l’absurde l’unicité de ce couple 𝑛−𝑢
Montrer n divisible par d si seulement si + (a+1) .u
10
5. Deduire théorème de la devision euclidienne pour tout a
est divisible par d
et b de Z avec a non nul

Ex 6 (nombre-somme de diviseurs)
Ex 5 (critères de divisibilité)
α α α
soit 𝑝1 1 .𝑝2 2 …. 𝑝𝑘 𝑘 la décomposition de n en produit de
Soient n ∈ ℕ et u le chiffre des unité de n et a de ℕ
facteurs premiers
1. Un nombre determine par 1
1. Nombre de diviseurs
Soit d=10a +1
on definie la fonction nombre de diviseurs strictement
a) Montrer que n divisible par d si seulement si
𝑛−𝑢
positifs d(n) par d(n)= ∑𝑑/𝑛 1 et ∀(n,m)∈ℕ
- a .u est divisible par d (m^n=1 ⇒d(n.m)=d(n).d(m) )
10
b) Application : est-ce-que 31 divise 30750 ? a) Calculer d(𝑝 𝛼 ) pour un p premier
2. Un nombre determie par 3 b) Montrer que d(n) = ∏𝑘 𝑖=1( α𝑖 + 1)
Soit d =10a +3 c) Montrer que d(n) est impair si et seulement si n est un
a) Montrer n divisible par d si seulement si carré parfait
𝑛−𝑢 𝑛
+ (3a+1) .u est divisible par d 𝑛
d) Montrer que ∑𝑘=1 𝑑 (k)=∑ 𝐸( )
𝑛
10
𝑖=1 𝑖
b) Application : montrer que 4416 divisible par 46

2
 7° Douae Elhaouiti
2. Somme de diviseurs Ex 8 (valuation p-adique)

On designe par S(n) la somme des diviseurs d’un entier n

Soit n un entier et p un nombre premier
a) Calculer S(𝑝 𝛼 ) avec p un nompre premier
𝛼 +1 On appele valuation p-adique que l’on note vp(n) le plus grand
𝑝 𝑖 −1
b) Montrer par reccurance S(n)= ∏𝑘𝑖=1 𝑖 entier k tel que pk /n
𝑝𝑖 −1
𝑛
1 𝑛 𝑛 1. Montrer [vp(n)=k ⇔ ∃q∈Z ; q^p=1 et n=pk.q ]
c) Montrer que ∑𝑛
𝑘=1 𝑆(𝑘) = .∑ 𝐸 ( ) . (𝐸 ( ) + 1)
2 𝑖=1 𝑖 𝑖
2. Montrer que b/a si seulement si pour tout nombre
premier p on a : vp(b) ≤ vp(a)
Ex 7 (rapidité de l’algorithme d’Euclide) 3. Montrer que : vp(a .b) = vp(a) + vp(b)
4. Justifier l’egalite : vp(n) = ∑+∞
𝑘=0 𝟙𝑝𝑘 /𝑛
Soit a et b deux entier tel que 0 <a< b et soit la suite (bn) n∈ℕ ∞
𝑛
5. Deduire vp(n!)=∑ 𝐸 ( 𝑘 ) (voir Ex 2)
définie par b0 =a et b1 =b et pour tout n∈ℕ* bn-1 =qn .bn+bn+1 avec 𝑘=1 𝑝
qn et bn+1 sont resp le quotient et le reste de la division
euclidienne de bn-1 par bn
Ex 9 (petit théorème de Fermat)
1. Montrer que (bn) décroit et que qn ≥ 1 pour tout n ∈ℕ
2. Montrer que (∀k∈ℕ) bk ≥ 2. bk+2 Soit p un nombre premier
𝑎 √2.𝑎
3. Montrer b2k ≤
√22𝑘
et b2k-1 ≤
√22𝑘−1
1. Montrer que (∀𝑞 ∈ ℕ ) 1≤ q ≤ p ⇒ p /𝐶𝑝𝑘
4. Montrer que (bn) s’annulle à partir d’un certain rang 2. Montrer que (a+b)p ≡ ap+ bp mod(p) et que
𝑃
√2.𝑎 (∑𝑛𝑘=1 𝑎𝑘 )p ≡ ∑𝑛𝑘=1 𝑎𝑘 mod(p) ; avec (𝑎𝑛 ) n∈ℕ une famille
5. Soit bn le dernier reste non nul, montrer que bn-1 ≤
√2𝑛−1
des entiers
puis deduire n ≤ 2. 𝑙𝑜𝑔2 (2𝑎)
3. Deduire np ≡ n mod (p)
4. Montrer que si n^p=1 alors np-1 ≡ 1 mod (p)

3
 7° Douae Elhaouiti
Ex 10 (théorème de Wilson) b) Montrer que m parfait Ssi b=(S(b)-b)(2a+1 – 1)
c) montrer que b est premier puis que b = 2a+1 – 1
[ p est premier ⇔ (p-1) ! + 1 ≡ 0 mod (p) ] (en remarquant que S(b) = b + (S(b) − b) )
4. Déduire.
1. Montrer que si (p-1) ! + 1 ≡ 0 mod (p) alors p est premier
2. Soit p un nombre premier
a) Montrer que tout entier inferieurs a p admet un
seul inverse
b) Montrer ∀k ∈ [2,p[ (p-k)2 ≢ 1 mod (p) Ex 12 (nombre de Carmichael)
c) Deduire que (p-2) ! ≡ 1 mod (p)
d) Deduire pour (p-1) ! . Un nombre composée n de un nombre de Cramichael ssi pour
tout nombre premier p on a : 𝑝 𝑑𝑖𝑣𝑖𝑠𝑒 𝑛 ⇒
Ex 11 (nombre parfait)
𝑝2 𝑛𝑒 𝑑𝑖𝑣𝑖𝑠𝑒 𝑝𝑎𝑠 𝑛
{ (critére de Korselt)
𝑝 − 1 𝑑𝑖𝑣𝑖𝑠𝑒 𝑛 − 1
Un nombre parfait est un nombre dont la somme de ses
On considere un entier composée (non premier est superieur a 1)
diviseurs propres est égale à ce nombre ( les diviseurs de n
n= 𝑝1 𝑝2… 𝑝𝑘 tel que pour tout i ∈[1 ,k] 𝑝𝑖 − 1 𝑑𝑖𝑣𝑖𝑠𝑒 𝑛 − 1
différents de n)
1. Montrer que tout les nbrs premiers ne sont pas parfais 1. Montrer que pour tout entier a si a^n=1 alors a^𝑝𝑖 =1
2. Soit n ∈ℕ et m= 2𝑛−1(2𝑛 − 1 ) on suppose que 2𝑛 − 1 2. Montrer que si a^n=1 alors 𝑎𝑝𝑖 −1 ≡ 1 𝑚𝑜𝑑 (𝑝𝑖 )
est premier 3. En deduire que 𝑎𝑛−1 ≡ 1 𝑚𝑜𝑑 (𝑝𝑖 )
a) Determiner la décomposition et les diviseurs de m 4. Montrer que 𝑝1 𝑝2… 𝑝𝑘 est divise 𝑎𝑛−1 − 1
b) Déduire que m est parfait 5. Deduire que pour tout entier premier avec n on a 𝒂𝒏−𝟏 ≡
3. Soit m =2a .b un nombre parfait avec a ≥ 1 et b impair et 𝟏 𝒎𝒐𝒅 (𝒏)
soit S(m) la somme des diviseurs positifs de m
a) Calculer S(m) en fonction de m et montrer que
S(m) =(2a+1 – 1) . S(b) (voir Ex 6)

4
 7° Douae Elhaouiti
Ex 13 (une application arithmetique) b) Monter que (∀ 𝑛 ≥ 1) 1 ≤ 𝑝(𝑛) ≤ 9 (1 + log(𝑛))
𝑛
c) Deduire la limite de ( √𝑝(𝑛))n≥1
1. Montre que lensemble des solution de l’equation
195x -232y=1 est S= { (163+232k ; 137+195k) / k∈ Z } ;
trouver l’entier naturel d tel que d ≤232 et Bonus
195d≡ 1 mod (232)
𝐸 ⟶𝐸 1. Soient a et b 2 entiers positifs
2. Soit E = [0,232] on pose U : 𝑎⟶𝑈(𝑎) avec U(a) est le restre
𝑎
Montrer que a^b= a + b − ab + 2.∑𝑏−1
𝑘=1 𝐸 (𝑘. )
de la div euclidienne de 𝑎195 par 233 𝑏
Marcelo Polezzi.
a) Montrer que (∀𝑎 ∈ E*) 𝑎232 ≡ 1 𝑚𝑜𝑑(233)

b) Soit a,b ∈ E , montrer que si U(a)=U(b) alors a=b 2. Touver x et y sachant que l’entier n=x1527y divisible par
4 et congru a 5 modulo 11.
c) On pose b=U(a) Trouver a en fonction de b
Olympiades Hong-Kong 2001
d) Deduire que U est bijective, Exprimer U-1
3. Soit n et m 2 entier on utilisant formule de lagrange
(𝟐𝒎)!×(𝟐𝒏)!
montrer que est un entier.
𝒎!×𝒏!×(𝒎+𝒏)!
Ex 14 (somme des chiffre d’un entier)
Olympiades internationales 1972
𝑝
Soit n=∑𝑘=0 𝑎𝑘 . 10𝑘 4. Montrer que pour tout entier naturel n
1. Donner le nombre de chiffre de n en fonction de n 2𝑛+1 𝑑𝑖𝑣𝑖𝑠𝑒 𝐸((1 + √3)2𝑛+1)
(càd p en fonction de n)
2. Soit p(n) la somme des chiffres de n
𝑝(𝑛+1)
Fin
a) Montrer que la suite ( )
𝑛∈ℕ∗ est bornée
𝑝(𝑛)
et diverge Douae Elhaouiti
2022-23