Lucrare

Soluţii

28 aprilie 2015

Varianta 1
I 1 Definiţi noţiunile de număr prim şi număr ireductibil.

Soluţie. Vezi Curs 6 Definiţiile 1 şi 2

Definiţie. Numărul ı̂ntreg p se numeşte număr prim dacă p 6= 0, p 6= ±1 şi p|ab, cu a, b ∈ Z implică p|a
sau p|b.
Definiţie. Numărul ı̂ntreg p se numeşte număr ireductibil (sau indecompozabil) dacă p 6= 0, p 6= ±1 şi
singurii săi divizori sunt ±1, ±p.

2 Demonstraţi că, ı̂n mulţimea numerelor naturale, orice număr prim este ireductibil.

Soluţie. Vezi Curs 6 Teorema 2

Fie p ∈ N, p număr prim. Vrem să demonstrăm că p este ireductibil. Fie d ∈ N un divizor al său, adică
d|p. Rezultă că există a ∈ N astfel ı̂ncât da = p. În particular, p|ad. Cum p este prim, apar două cazuri:
i p|d. Cum d|p ⇒ d = ±p.
p=ad
ii p|a. Cum p = ad ⇒ a|p ⇒ a = ±p ===⇒ d = ±1.
Rezultă că d ∈ {±1, ±p}, deci p este ireductibil, ceea ce ı̂ncheie demonstraţia.

3 Enunţaţi Principiul Bunei Ordonări ı̂n mulţimea numerelor naturale.

Soluţie. Vezi Curs 2 Teorema 4

Teoremă. (Principiul Bunei Ordonări, PBO) Mulţimea N ı̂nzestrată cu relaţia de ordine totală ≤ este
o mulţime bine ordonată.

4 Demonstraţi Lema lui Euclid: dacă a, b, c ∈ N∗ , a|bc şi (a, b) = 1, atunci a|c.

Soluţie. Vezi Cursul 5 Propoziţia 5.3

(a, b) = 1 ⇒ ∃u, v ∈ Z astfel ı̂ncât au + bv = 1. Înmulţind cu c, rezultă că acu + bcv = c. Cum
a|bc ⇒ a|(acu + bcv) ⇒ a|c.

II 1 Determinaţi toţi divizorii numărului 252.

1
 Soluţie.
252 = 22 × 32 × 7.
Rezultă că divizorii naturali ai lui 252 sunt de forma 2a ×3b ×7c unde a ∈ {0, 1, 2}, b ∈ {0, 1, 2}, c ∈ {0, 1}.
Aceştia sunt:
20 × 30 × 70 = 1,
20 × 30 × 71 = 7,
20 × 31 × 70 = 3,
20 × 31 × 71 = 21,
20 × 32 × 70 = 9,
20 × 32 × 71 = 63,
21 × 30 × 70 = 2,
21 × 30 × 71 = 14,
21 × 31 × 70 = 6,
21 × 31 × 71 = 42,
21 × 32 × 70 = 18,
21 × 32 × 71 = 126,
22 × 30 × 70 = 4,
22 × 30 × 71 = 28,
22 × 31 × 70 = 12,
22 × 31 × 71 = 84
22 × 32 × 70 = 36,
22 × 32 × 71 = 252
N = {1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 126, 252}. Divizorii ı̂ntregi
Ordonând crescător: D252
Z
sunt: D252 = {±1, ±2, ±3, ±4, ±6, ±7, ±9, ±12, ±14, ±18, ±21, ±28, ±36, ±42, ±63, ±84, ±126, ±252}.

2 Determinaţi, folosind algoritmul lui Euclid, cel mai mare divizor comun al numerelor 252 şi 75; scrieţi
cel mai mare divizor comun ca o combinaţie liniară, cu coeficienţi ı̂ntregi, a numerelor 252 şi 75.

Soluţie. Vezi Fişa 5 Exerciţiul 2

252 = 75 × 3 + 27
75 = 27 × 2 + 21
27 = 21 × 1 + 6
21 = 6 × 3 + 3
6 = 3 × 2 + 0.
Rezultă că cel mai mare divizor comun al numerelor 252 şi 75 este (252, 75) = 3.
Urmărind algoritmul lui Euclid, obţinem 3 = 21−3×6 = (75−2×27)−3(27−21) = 75−5×27+3×21 =
75 − 5 × 27 + 3(75 − 2 × 27) = 4 × 75 − 11 × 27 = 4 × 75 − 11(252 − 3 × 75) = 37 × 75 − 11 × 252.

3 Demonstraţi, folosind principiul inducţiei matematice, că 2n > n, oricare ar fi n ∈ N.

2
 Soluţie. Ne propunem să demonstrăm P (n) : 2n > n, ∀n ∈ N.
Pentru n = 0, P (0) : 20 > 0 este adevărată.
Pasul I: Etapa de verificare [n = 1]. P (1) : 21 > 1 este adevărată.
Pasul II: Pasul inductiv [∀k ≥ 1, P (k) ⇒ P (k + 1)]. Presupunem că P (k) este adevărată, adică 2k > k.
2k≥k+1 pentru k≥1
Înmulţind inegalitatea cu 2, rezultă că 2 × 2k > 2k ⇒ 2k+1 > 2k ============⇒ 2k+1 > k + 1, deci
P (k + 1) este adevărată.
Folosind principiul inducţiei matematice, rezultă că P (n) : 2n > n este adevărată ∀n ∈ N∗ . Cum P (0)
este, de asemenea adevărată, rezultă că: 2n > n, ∀n ∈ N.

4 (a) Scrieţi numărul 79(10) ı̂n baza 5.

(b) Determinaţi baza de numeraţie u ı̂n care 371(u) − 355(u) divide 477(u) − 433(u) .

Soluţie. (a)
79 = 5 × 15 + 4
15 = 5 × 3 + 0
Deci, 79(10) = 304(5) .
(b) Vezi Fişa 3 Exerciţiul 22
Să observăm, pentru ı̂nceput că u ∈ N, u > 7.
371(u) − 355(u) = (3u2 + 7u + 1) − (3u2 + 5u + 5) = 2u − 4.
477(u) − 433(u) = (4u2 + 7u + 7) − (4u2 + 3u + 3) = 4u + 4.
(2u−4)|(4u−8)
(371(u) − 355(u) )|(477(u) − 433(u) ) ⇒ (2u − 4)|(4u + 4) =========⇒ (2u − 4)|((4u + 4) − (4u − 8)) ⇒
u∈N,u>7
(2u − 4)|12 =====⇒ 2u − 4 = 12 ⇒ u = 8.

5 (a) Arătaţi că dacă p ∈ N, p > 4 este prim, atunci p2 este de forma 4k + 1 şi de asemenea, de forma
3h + 1 (h, k ∈ N∗ ).
(b) Deduceţi că restul ı̂mpărţirii lui p2 la 12 este 1.

k=a2 +a∈N∗
Soluţie. (a) p > 4 prim ⇒ p impar, adică ∃a ∈ N∗ astfel ı̂ncât p = 2a + 1 ⇒ p2 = 4a2 + 4a + 1 =======⇒
p2 = 4k + 1.
p > 4 prim ⇒ p nu este divizibil cu 3, adică p este de forma 3b + 1 sau 3b + 2, unde b ∈ N∗ .
h=3b2 +2b∈N∗
i p = 3b + 1, b ∈ N∗ ⇒ p2 = 9b2 + 6b + 1 ========⇒ p2 = 3h + 1.
h=3b2 +4b+1∈N∗
ii p = 3b + 2, b ∈ N∗ ⇒ p2 = 9b2 + 12b + 4 ==========⇒ p2 = 3h + 1.
(4,3)=1
(b) Folosind punctul anterior, rezultă că p2 = 4k +1 = 3h+1 unde h, k ∈ N∗ . Rezultă că 4k = 3h ====⇒
.
k .. 3 ⇒ ∃s ∈ N∗ astfel ı̂ncât k = 3s ⇒ p2 = 12s + 1, ceea ce ı̂ncheie demonstraţia.

3
Varianta 2
I 1 Enunţaţi Teorema ı̂mpărţirii cu rest.

Soluţie. Vezi Curs 4 Teorema 1

Teoremă. (Teorema ı̂mpărţirii cu rest - TIR)
(i) Pentru orice două numere naturale a şi b, b 6= 0, există şi sunt unice numerele naturale q şi r astfel
ı̂ncât
a = bq + r şi 0 ≤ r < b.
(ii) Pentru orice două numere ı̂ntregi a şi b, b 6= 0, există şi sunt unice numerele ı̂ntregi q şi r astfel
ı̂ncât
a = bq + r şi 0 ≤ r < |b|.

2 Demonstraţi Teorema lui Euclid: există o infinitate de numere prime ı̂n N.

Soluţie. Vezi Curs 7 Teorema 1

Raţionăm prin reducere la absurd. Presupunem că mulţimea tuturor numerelor naturale prime este
finită, {p1 , p2 , . . . , pr }. Fie n = p1 p2 . . . pr + 1. Atunci, oricare ar fi i ∈ {1, . . . , r}, pi < n, deci n nu
este prim. Rezultă că n are un divizor prim, fie acesta pj pentru un j ∈ {1, . . . , r}, pj |n. Dar evident
pj |p1 p2 . . . pr , deci pj |1, ceea ce este absurd. Rezultă că presupunerea făcută este falsă, deci există o
infinitate de numere prime.

3 Definiţi noţiunile de cel mai mare divizor comun şi cel mai mic multiplu comun ı̂n N.

Soluţie. Vezi Curs 5 Definiţiile 1 şi 3

Definiţie. Fie a, b ∈ N, a 6= 0 sau b 6= 0. Spunem că numărul natural d este cel mai mare divizor comun
al numerelor a şi b, şi notăm d = (a, b), dacă:
1. d|a şi d|b;
2. dacă d0 ∈ N este divizor comun al numerelor a şi b, atunci d0 |d.
Dacă a = b = 0, definim (a, b) = 0.
Definiţie. Fie a, b ∈ N. Spunem că numărul natural m este cel mai mic multiplu comun al numerelor a
şi b, şi notăm m = [a, b], dacă:
1. a|m şi b|m;
2. dacă m0 ∈ N este multiplu comun al numerelor a şi b, atunci m|m0 .

4 Demonstraţi că dacă a, b, c ∈ N, a|c, b|c şi (a, b) = 1 atunci ab|c.

Soluţie. Vezi Cursul 5 Propoziţia 5.4

(a, b) = 1 ⇒ ∃u, v ∈ Z astfel ı̂ncât au + bv = 1. Înmulţind cu c, rezultă că acu + bcv = c.
acu+bcv=c
Pe de altă parte, a|c şi b|c ⇒ ab|bc şi ab|ac ⇒ ab|(acu + bcv) ======⇒ ab|c.

II 1 Determinaţi toţi divizorii numărului 140.

4
 Soluţie.
140 = 22 × 5 × 7.
Rezultă că divizorii naturali ai lui 140 sunt de forma 2a × 3b × 7c unde a ∈ {0, 1, 2}, b ∈ {0, 1}, c ∈ {0, 1}.
Aceştia sunt:
20 × 50 × 70 = 1,
20 × 50 × 71 = 7,
20 × 51 × 70 = 5,
20 × 51 × 71 = 35,
21 × 50 × 70 = 2,
21 × 50 × 71 = 14,
21 × 51 × 70 = 10,
21 × 51 × 71 = 70,
22 × 50 × 70 = 4,
22 × 50 × 71 = 28,
22 × 51 × 70 = 20,
22 × 51 × 71 = 140
N
Ordonând crescător: D140 = {1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}. Z
Divizorii ı̂ntregi sunt: D140 =
{±1, ±2, ±4, ±5, ±7, ±10, ±14, ±20, ±28, ±35, ±70, ±140}.

2 Determinaţi, folosind algoritmul lui Euclid, cel mai mare divizor comun al numerelor 231 şi 140; scrieţi
cel mai mare divizor comun ca o combinaţie liniară, cu coeficienţi ı̂ntregi, a numerelor 231 şi 140.

Soluţie. Vezi Fişa 5 Exerciţiul 2

231 = 140 × 1 + 91
140 = 91 × 1 + 49
91 = 49 × 1 + 42
49 = 42 × 1 + 7
42 = 7 × 6 + 0.
Rezultă că cel mai mare divizor comun al numerelor 231 şi 140 este (231, 140) = 7.
Urmărind algoritmul lui Euclid, obţinem 7 = 49 − 42 = (140 − 91) − (91 − 49) = 140 − 2 × 91 + 49 =
140 − 2 × 91 + (140 − 91) = 2 × 140 − 3 × 91 = 2 × 140 − 3(231 − 140) = −3 × 231 + 5 × 140.

3 Demonstraţi, folosind principiul inducţiei matematice, că 2n+2 > 2n + 5, oricare ar fi n ∈ N∗ .

Soluţie. Ne propunem să demonstrăm P (n) : 2n+2 > 2n + 5, ∀n ∈ N∗ .

Pasul I: Etapa de verificare [n = 1]. P (1) : 23 > 7 este adevărată.
Pasul II: Pasul inductiv [∀k ≥ 1, P (k) ⇒ P (k + 1)]. Presupunem că P (k) este adevărată, adică 2k+2 >
4k+10≥2k+7 pentru k≥1
2k+5. Înmulţind inegalitatea cu 2, rezultă că 2×2k+2 > 2(2k+5) ⇒ 2k+3 > 4k+10 ===============⇒
2(k+1)+2 > 2(k + 1) + 5, deci P (k + 1) este adevărată.
Folosind principiul inducţiei matematice, rezultă că P (n) : 2n+2 > 2n + 5 este adevărată ∀n ∈ N∗ .

4 (a) Scrieţi numărul 79(10) ı̂n baza 6.

(b) Determinaţi baza de numeraţie u ı̂n care 371(u) − 355(u) divide 4 · 11(u) .

5
 Soluţie. (a)
79 = 6 × 13 + 1
13 = 6 × 2 + 1
Deci, 79(10) = 211(6) .
(b) Vezi Fişa 3 Exerciţiul 22
Să observăm, pentru ı̂nceput că u ∈ N, u > 7.
371(u) − 355(u) = (3u2 + 7u + 1) − (3u2 + 5u + 5) = 2u − 4.
4 · 11(u) = 4(u + 1) = 4u + 4.
(2u−4)|(4u−8)
(371(u) − 355(u) )|4 · 11(u) ⇒ (2u − 4)|(4u + 4) =========⇒ (2u − 4)|((4u + 4) − (4u − 8)) ⇒
u∈N,u>7
(2u − 4)|12 =====⇒ 2u − 4 = 12 ⇒ u = 8.

5 (a) Să se arate că dacă p ∈ N este un număr prim, p > 4, atunci p este de forma 6k + 1 sau de forma
6k − 1 (k ∈ N∗ ).
(b) Deduceţi că restul ı̂mpărţirii lui p2 la 12 este 1.

Soluţie. (a) p ∈ N, p > 4 ⇒ p poate fi de forma 6k, 6k + 1, 6k + 2, 6k + 3, 6k − 2, 6k − 1, k ∈ N∗ .

. . . .
6k..2, (6k+2)..2, (6k+3)..3, (6k−2)..2
Pe de altă parte, p > 4 prim ⇒ p impar şi p nu este divizibil cu 3 ======================⇒ p
este de forma 6k + 1 sau de forma 6k − 1 (k ∈ N∗ ).
(b) Folosind punctul anterior, rezultă că p2 este de forma (6k ±1)2 = 36k 2 ±12k +1, deci restul ı̂mpărţirii
lui p2 la 12 este 1.

6
Varianta 3
I 1 Enunţaţi Teorema fundamentală a aritmeticii.

Soluţie. Vezi Curs 5 Teoremele 11 şi 12

Teoremă. (Teorema fundamentală a aritmeticii pentru numere naturale) Fie a ∈ N, a > 1. Atunci a
se scrie ı̂n mod unic, până la ordinea factorilor, ca un produs de numere prime.
Teoremă. (Teorema fundamentală a aritmeticii pentru numere ı̂ntregi) Fie a ∈ Z, |a| > 1. Atunci a se
scrie ı̂n mod unic, până la ordinea factorilor şi semnul acestora, ca un produs de numere prime.

2 Demonstraţi existenţa descompunerii oricărui număr natural n > 1 ı̂n factori indecompozabili.

Soluţie. Fie S = {n ∈ N \ {0, 1}|n nu poate fi scris a produs de factori indecompozabili}. Presupunem,
prin reducere la absurd, că această mulţime este nevidă. Cum S ⊂ N ⇒ S are un cel mai mic element.
Fie acesta n. Dacă n este indecompozabil ⇒ n poate fi scris ca produs de 1 factor indecompozabil, n
ı̂nsuşi, deci n ∈
/ S. Contradicţie. Deci n nu este indecompozabil ⇒ n admite un divizor a 6= 1, a 6= n ⇒
b,c<n
1 < a < n ⇒ ∃b ∈ N, 1 < b < n astfel ı̂ncât n = bc ===⇒ b, c ∈ S ⇒ b şi c admit scriere ca produs
de factori indecompozabili: b = b1 . . . bm , c = c1 . . . ck ⇒ n = b1 . . . bm c1 . . . ck , deci n are scriere ca
produs de factori indecompozabili ⇒ n ∈ / S ⇒ presupunerea făcută este falsă ⇒ S = ∅, ceea ce ı̂ncheie
demonstraţia.

3 Demonstraţi că dacă a, b, q, r ∈ N∗ , a = bq + r atunci (a, b) = (b, r).

Soluţie. Vezi Curs 5 Lema 6 Fie d = (a, b), d0 = (b, r). Deoarece d|a şi d|b, rezultă d|r, deci d|d0 . La
fel, deoarece d0 |r şi d0 |b, rezultă d0 |a, deci d0 |d. Rezultă deci că d = d0

4 Definiţi mulţimea numerelor ı̂ntregi, plecând de la mulţimea numerelor naturale.

Soluţie. Vezi Cursul 1 Secţiunea 1

Fie N mulţimea numerelor naturale. Pe mulţimea N × N definim relaţia ”∼” prin (m, n) ∼ (p, q) dacă
m + q = n + p.
Se demonstrează că ”∼” este o relaţie de echivalenţă pe mulţimea N × N. Clasa de echivalenţă cores-
punzătoare perechii (m, n) se notează

(m, n) = {(p, q) ∈ N × N|(m, n) ∼ (p, q)}

şi se numeşte număr ı̂ntreg. Mulţimea claselor de echivalenţă se numeşte mulţimea numerelor ı̂ntregi şi
se notează cu Z. Avem deci
Z = (N × N)/ ∼ .

II 1 Determinaţi toţi divizorii numărului 132.

Soluţie.
132 = 22 × 3 × 11.
Rezultă că divizorii naturali ai lui 132 sunt de forma 2a ×3b ×11c unde a ∈ {0, 1, 2}, b ∈ {0, 1}, c ∈ {0, 1}.
Aceştia sunt:
20 × 30 × 110 = 1,
20 × 30 × 111 = 11,
20 × 31 × 110 = 3,

7
 20 × 31 × 111 = 33,
21 × 30 × 110 = 2,
21 × 30 × 111 = 22,
21 × 31 × 110 = 6,
21 × 31 × 111 = 66,
22 × 30 × 110 = 4,
22 × 30 × 111 = 44,
22 × 31 × 70 = 12,
22 × 31 × 111 = 132
N
Ordonând crescător: D132 = {1, 2, 3, 4, 6, 11, 12, 22, 33, 44, 66, 132}. Z
Divizorii ı̂ntregi sunt: D140 =
{±1, ±2, ±3, ±4, ±6, ±11, ±12, ±22, ±33, ±44, ±66, ±132}.

2 Determinaţi, folosind algoritmul lui Euclid, cel mai mare divizor comun al numerelor 35 şi 132; scrieţi
cel mai mare divizor comun ca o combinaţie liniară, cu coeficienţi ı̂ntregi, a numerelor 35 şi 132.

Soluţie. Vezi Fişa 5 Exerciţiul 2

132 = 35 × 3 + 27
35 = 27 × 1 + 8
27 = 8 × 3 + 3
8=3×2+2
3=2×1+1
2 = 1 × 2 + 0.
Rezultă că cel mai mare divizor comun al numerelor 132 şi 35 este (132, 35) = 1.
Urmărind algoritmul lui Euclid, obţinem 1 = 3 − 2 = (27 − 3 × 8) − (8 − 2 × 3) = 27 − 4 × 8 + 2 × 3 =
27−4×8+2(27−3×8) = 3×27−10×8 = 3×27−10(35−27) = 13×27−10×35 = 13(132−3×35)−10×35 =
13 × 132 − 49 × 35.

3 Demonstraţi, folosind principiul inducţiei matematice, că 3n ≥ 3n, oricare ar fi n ∈ N.

Soluţie. Ne propunem să demonstrăm P (n) : 3n ≥ 3n, ∀n ∈ N.

Pasul I: Etapa de verificare [n = 1]. P (1) : 31 ≥ 3 · 1 este adevărată.
Pasul II: Pasul inductiv [∀k ≥ 1, P (k) ⇒ P (k + 1)]. Presupunem că P (k) este adevărată, adică 3k > 3k.
9k≥3k+3 pentru k≥1
Înmulţind inegalitatea cu 3, rezultă că 3 · 3k ≥ 3 · 3k ⇒ 3k+1 ≥ 9k =============⇒ 3k+1 ≥ 3(k + 1),
deci P (k + 1) este adevărată.
Folosind principiul inducţiei matematice, rezultă că 3n ≥ 3n, ∀n ∈ N∗ .

4 (a) Scrieţi numărul 79(10) ı̂n baza 4.

(b) Determinaţi baza de numeraţie u ı̂n care 361(u) − 345(u) divide 477(u) − 431(u) .

Soluţie. (a)
79 = 4 × 19 + 3
19 = 4 × 4 + 3
4 = 4 × 1 + 0.
Deci, 79(10) = 1033(4) .

8
 (b) Vezi Fişa 3 Exerciţiul 22
Să observăm, pentru ı̂nceput că u ∈ N, u > 7.
361(u) − 345(u) = (3u2 + 6u + 1) − (3u2 + 4u + 5) = 2u − 4.
477(u) − 433(u) = (4u2 + 7u + 7) − (4u2 + 3u + 3) = 4u + 4.
(2u−4)|(4u−8)
(361(u) − 345(u) )|(477(u) − 433(u) ) ⇒ (2u − 4)|(4u + 4) =========⇒ (2u − 4)|((4u + 4) − (4u − 8)) ⇒
u∈N,u>7
(2u − 4)|12 =====⇒ 2u − 4 = 12 ⇒ u = 8.

5 (a) Dacă p ∈ N este prim şi p > 5, atunci p2 este de forma 5k + 1 sau de forma 5k − 1 (k ∈ N∗ ).
(b) Deduceţi că 10 divide unul dintre numerele p2 − 1 sau p2 + 1.

Soluţie. (a) p > 5 prim ⇒ p nu este divizibil cu 5. Apar următoarele cazuri:

hk=5b2 ±2b∈N∗
i p = 5b ± 1, b ∈ N∗ ⇒ p2 = 25b2 ± 10b + 1 =========⇒ p2 = 5k + 1.
k=5b2 ±4b+1∈N∗
ii p = 5b ± 2, b ∈ N∗ ⇒ p2 = 25b2 ± 20b + 4 ==========⇒ p2 = 5k − 1.
(b) p > 5 prim ⇒ p este impar, deci 2|(p2 −1) şi 2|(p2 +1). Folosind punctul anterior, rezultă următoarele
cazuri:
2|(p2 −1), (2,5)=1
i p2 = 5k + 1, k ∈ N∗ ⇒ 5|(p2 − 1) ==========⇒ 10|(p2 − 1).
2|(p2 +1), (2,5)=1
ii p2 = 5k − 1, k ∈ N∗ ⇒ 5|(p2 + 1) ==========⇒ 10|(p2 + 1).

9
Varianta 4
I 1 Definiţi noţiunea de cel mai mare divizor comun.

Soluţie. Vezi Curs 5 Definiţia 1

Definiţie. Fie a, b ∈ Z, a 6= 0 sau b 6= 0. Spunem că numărul ı̂ntreg d este cel mai mare divizor comun
al numerelor a şi b, şi notăm d = (a, b), dacă:
1. d|a şi d|b;
2. dacă d0 ∈ Z este divizor comun al numerelor a şi b, atunci d0 |d.
Dacă a = b = 0, definim (a, b) = 0.

2 Demonstraţi existenţa şi unicitatea celui mai mare divizor comun al numerelor naturale nenule a şi b.

Soluţie. Vezi Curs 5 Propoziţia 1 şi Teorema 2

Folosim următorul rezultat
Propoziţie. Fie a, b ∈ Z şi d = (a, b). Fie δ ∈ Z astfel ı̂ncât următoarele proprietăţi sunt verificate:
1’. δ este divizor comun al numerelor a şi b;
2’. dacă d0 ∈ Z este divizor comun al numerelor a şi b, atunci d0 |δ.
Atunci d = δ.
Demonstraţie: Deoarece δ este un divizor comun al numerelor a şi b, atunci, conform proprietăţii 2 din
Definiţia celui mai mare divizor comun, δ|d. Rezultă că |δ| ≤ |d|. Cum d ∈ N obţinem δ ≤ d.
Pe de altă parte, şi d este un divizor comun al numerelor a şi b. Atunci conform proprietăţii 2’ din
enunţul propoziţiei, d ≤ δ. Rezultă deci că d = δ.
Trecem la demonstraţia rezultatului:
Teoremă. Oricare ar fi a, b ∈ Z, cel mai mare divizor comun al lor există şi este unic.
Demonstraţie: Dacă a = b = 0 atunci (a, b) = 0 prin definiţie, deci există şi este unic.
Presupunem că cel puţin unul din cele două numere este nenul, de exemplu b 6= 0. Fie mulţimea
M = {c ∈ N|c|a şi c|b}. Mulţimea M este nevidă, deoarece 1 ∈ M şi mărginită, deoarece c ≤ |b|,
∀c ∈ M . Atunci M are un cel mai mare element d. Este uşor de verificat că acesta verifică cele două
condiţii din Propoziţie, deci d = (a, b).
Unicitatea rezultă imediat din faptul că (a, b) satisface condiţia 20 din Propoziţie.

3 Enunţaţi Teorema Numerelor Prime.

Soluţie. Vezi Curs 2 Teorema 4

Teoremă. (Teorema numerelor prime) Dacă n ∈ N, n ≥ 2, atunci

π(n)
lim n = 1.
n→∞
ln n

a b


4 Demonstraţi că dacă a, b ∈ Z şi (a, b) = d, atunci d, d = 1.

Soluţie. Vezi Cursul 5 Propoziţia 5.2

Rezultatul este valabil dacă (a, b) 6= 0. (a, b) = d ⇒ d|a şi d|b ⇒ ∃u, v ∈ Z astfel ı̂ncât a = du, b = dv.
d=(a,b)
Fie (u, v) = d0 ⇒ d0 d|a şi d0 d|b ====⇒ dd0 |d ⇒ d0 = 1 ceea ce ı̂ncheie demonstraţia.

10
II 1 Determinaţi toţi divizorii numărului 312.

Soluţie.
312 = 23 × 3 × 13.
Rezultă că divizorii naturali ai lui 312 sunt de forma 2a × 3b × 13c unde a ∈ {0, 1, 2, 3}, b ∈ {0, 1},
c ∈ {0, 1}. Aceştia sunt:
20 × 30 × 130 = 1,
20 × 30 × 131 = 13,
20 × 31 × 130 = 3,
20 × 31 × 131 = 39,
21 × 30 × 130 = 2,
21 × 30 × 131 = 26,
21 × 31 × 130 = 6,
21 × 31 × 131 = 78,
22 × 30 × 130 = 4,
22 × 30 × 131 = 52,
22 × 31 × 130 = 12,
22 × 31 × 131 = 156,
23 × 30 × 130 = 8,
23 × 30 × 131 = 104,
23 × 31 × 130 = 24,
23 × 31 × 131 = 312.
N = {1, 2, 3, 4, 6, 8, 12, 13, 16, 24, 26, 39, 52, 78, 156, 312}. Divizorii ı̂ntregi sunt:
Ordonând crescător: D312
Z = {±1, ±2, ±3, ±4, ±6, ±8, ±12, ±13, ±16, ±24, ±26, ±39, ±52, ±78, ±156, ±312}.
D252

2 Determinaţi, folosind algoritmul lui Euclid, cel mai mare divizor comun al numerelor 312 şi 75; scrieţi
cel mai mare divizor comun ca o combinaţie liniară, cu coeficienţi ı̂ntregi, a numerelor 312 şi 75.

Soluţie. Vezi Fişa 5 Exerciţiul 2

312 = 75 × 4 + 12
75 = 12 × 6 + 3
12 = 3 × 4 + 0.
Rezultă că cel mai mare divizor comun al numerelor 312 şi 75 este (312, 75) = 3.
Urmărind algoritmul lui Euclid, obţinem 3 = 75 − 6 × 12 = 75 − 6(312 − 4 × 75) = 25 × 75 − 6 × 312.

3 Demonstraţi, folosind principiul inducţiei matematice, că 2n > 2n − 1, oricare ar fi n ∈ N.

11
 Soluţie. Ne propunem să demonstrăm P (n) : 2n > 2n − 1, ∀n ∈ N.
Pentru n = 0, P (0) : 20 > 2 · 0 − 1 este adevărată.
Pentru n = 1, P (1) : 21 > 2 · 1 − 1 este adevărată.
Pasul I: Etapa de verificare [n = 2]. P (2) : 22 > 2 · 2 − 1 este adevărată.
Pasul II: Pasul inductiv [∀k ≥ 2, P (k) ⇒ P (k + 1)]. Presupunem că P (k) este adevărată, adică 2k >
4k−2≥2k+1 pentru k≥2
2 · k − 1. Înmulţind inegalitatea cu 2, rezultă că 2 × 2k > 2(2k − 1) ⇒ 2k+1 > 4k − 2 ===============⇒
2k+1 > 2k + 1, deci P (k + 1) este adevărată.
Folosind principiul inducţiei matematice, rezultă că P (n) : 2n > 2n − 1 este adevărată ∀n ∈ N \ {0, 1}.
Cum P (0), P (1) sunt, de asemenea adevărate, rezultă că: 2n > 2n − 1, ∀n ∈ N.

4 (a) Scrieţi numărul 85(10) ı̂n baza 7.

(b) Determinaţi baza de numeraţie u ı̂n care 571(u) − 555(u) divide 377(u) − 333(u) .

Soluţie. (a)
85 = 7 × 12 + 1
12 = 7 × 1 + 5
Deci, 85(10) = 151(7) .
(b) Vezi Fişa 3 Exerciţiul 22
Să observăm, pentru ı̂nceput că u ∈ N, u > 7.
571(u) − 555(u) = (5u2 + 7u + 1) − (5u2 + 5u + 5) = 2u − 4.
377(u) − 333(u) = (3u2 + 7u + 7) − (3u2 + 3u + 3) = 4u + 4.
(2u−4)|(4u−8)
(571(u) − 555(u) )|(377(u) − 333(u) ) ⇒ (2u − 4)|(4u + 4) =========⇒ (2u − 4)|((4u + 4) − (4u − 8)) ⇒
u∈N,u>7
(2u − 4)|12 =====⇒ 2u − 4 = 12 ⇒ u = 8.

5 (a) Să se arate că dacă p ∈ N este un număr prim, p > 4, atunci p este de forma 6k + 1 sau de forma
6k + 5 (k ∈ N).
(b) Deduceţi că dacă p ∈ N, p > 4 este prim, atunci p2 + 2 este număr compus.

Soluţie. (a) p ∈ N, p > 4 ⇒ p poate fi de forma 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5, k ∈ N.

. . . .
6k..2, (6k+2)..2, (6k+3)..3, (6k+4)..2
Pe de altă parte, p > 4 prim ⇒ p impar şi p nu este divizibil cu 3 ======================⇒ p
este de forma 6k + 1 (k ∈ N∗ ) sau de forma 6k + 5 (k ∈ N).
(b) Folosind punctul anterior, rezultă două cazuri:
12k2 +4k+1>1, k>0
i p = 6k + 1, k ∈ N∗ ⇒ p2 + 2 = 36k 2 + 12k + 3 = 3(12k 2 + 4k + 1) ============⇒ p2 + 2 este
compus.
12k2 +20k+9>1
ii p = 6k + 5, k ∈ N ⇒ p2 + 2 = 36k 2 + 60k + 27 = 3(12k 2 + 20k + 9) =========⇒ p2 + 2 este
compus.

12
Varianta 5
I 1 Definiţi noţiunea de cel mai mic multiplu comun al numerelor ı̂ntregi a şi b.

Soluţie. Vezi Curs 5 Definiţia 3

Definiţie. Fie a, b ∈ Z. Spunem că numărul ı̂ntreg m este cel mai mic multiplu comun al numerelor a
şi b, şi notăm m = [a, b], dacă:
1. a|m şi b|m;
2. dacă m0 ∈ Z este multiplu comun al numerelor a şi b, atunci m|m0 .

2 Demonstraţi că dacă a, b ∈ N∗ , atunci (a, b) · [a, b] = a · b.

Soluţie. Vezi Curs 6 Teorema 2

Dacă (a, b) = 0, reultatul este verificat. Altfel, fie (a, b) = d ⇒ d|a şi d|b ⇒ ∃u, v ∈ Z astfel ı̂ncât
a = du, b = dv cu (u, v) = 1.
Vrem să arătăm că [a, b] = duv. duv = av ⇒ a|duv; duv = bu ⇒ b|duv.
Fie m0 astfel ı̂ncât a|m0 şi b|m0 ⇒ ∃α, β ∈ N∗ astfel ı̂ncât m0 = aα = bβ ⇒ duα = dvβ ⇒ uα =
(u,v)=1 . .
vβ ====⇒ α .. v ⇒ m0 .. m ceea ce ı̂ncheie demonstraţia.

3 Enunţaţi Principiul Trihotomiei ı̂n N.

Soluţie. Vezi Curs 2 Teorema 3

Teoremă. (Principiul trihotomiei, PT) Pentru două numere naturale m şi n una şi numai una din
următoarele relaţii are loc: m < n, m = n sau m > n.

4 Demonstraţi că dacă a ∈ N, a > 1 este compus, atunci există b, c ∈ N, 1 < b, c < a astfel ı̂ncât a = bc.

Soluţie. Vezi Cursul 6 Propoziţia 1

1<b<a
a este compus ⇒ ∃b ∈ N, b|a, b 6= 1, b 6= a ⇒ 1 < b < a. Cum b|a ⇒ ∃c ∈ N astfel ı̂ncât a = bc ====⇒
1 < c < a, ceea ce ı̂ncheie demonstraţia.

II 1 Determinaţi toţi divizorii numărului 220.

Soluţie.
220 = 22 × 5 × 11.
Rezultă că divizorii naturali ai lui 220 sunt de forma 2a ×5b ×11c unde a ∈ {0, 1, 2}, b ∈ {0, 1}, c ∈ {0, 1}.
Aceştia sunt:
20 × 50 × 110 = 1,
20 × 50 × 111 = 11,
20 × 51 × 110 = 5,
20 × 51 × 111 = 55,
21 × 50 × 110 = 2,
21 × 50 × 111 = 22,
21 × 51 × 110 = 20,
21 × 51 × 111 = 110,

13
 22 × 50 × 110 = 4,
22 × 50 × 111 = 44,
22 × 51 × 110 = 20,
22 × 51 × 111 = 220
N
Ordonând crescător: D220 = {1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220}. Divizorii ı̂ntregi sunt: D252
Z =
{±1, ±2, ±4, ±5, ±10, ±11, ±20, ±22, ±44, ±55, ±110, ±220}.

2 Determinaţi, folosind algoritmul lui Euclid, cel mai mare divizor comun al numerelor 231 şi 220; scrieţi
cel mai mare divizor comun ca o combinaţie liniară, cu coeficienţi ı̂ntregi, a numerelor 231 şi 220.

Soluţie. Vezi Fişa 5 Exerciţiul 2

231 = 220 × 1 + 11
220 = 11 × 20 + 0
Rezultă că cel mai mare divizor comun al numerelor 231 şi 220 este (231, 220) = 11.
Urmărind algoritmul lui Euclid, obţinem 11 = 231 − 220.

3 Demonstraţi, folosind principiul inducţiei matematice, că 3n+2 > 3n + 5, oricare ar fi n ∈ N.

Soluţie. Ne propunem să demonstrăm P (n) : 3n+2 > 3n + 5, ∀n ∈ N.

Pasul I: Etapa de verificare [n = 0]. P (0) : 32 > 5 este adevărată.
Pasul II: Pasul inductiv [∀k ≥ 0, P (k) ⇒ P (k + 1)]. Presupunem că P (k) este adevărată, adică 3k+2 >
9k+15≥3k+8 pentru k≥0
3k+5. Înmulţind inegalitatea cu 3, rezultă că 3×3k+2 > 3(3k+5) ⇒ 3k+3 > 9k+15 ===============⇒
3(k+1)+2 > 3(k + 1) + 5, deci P (k + 1) este adevărată.
Folosind principiul inducţiei matematice, rezultă că P (n) : 3n+2 > 3n + 5 este adevărată ∀n ∈ N.

4 (a) Scrieţi numărul 91(10) ı̂n baza 8.

(b) Determinaţi baza de numeraţie u ı̂n care 672(u) − 656(u) divide 2 · 22(u) .

Soluţie. (a)
91 = 8 × 11 + 3
11 = 8 × 1 + 3
Deci, 91(10) = 133(8) .
(b) Vezi Fişa 3 Exerciţiul 22
Să observăm, pentru ı̂nceput că u ∈ N, u > 7.
672(u) − 656(u) = (6u2 + 7u + 2) − (6u2 + 5u + 6) = 2u − 4.
2 · 22(u) = 2(2u + 2) = 4u + 4.
(2u−4)|(4u−8)
(672(u) − 656(u) )|(2 · 22(u) ) ⇒ (2u − 4)|(4u + 4) =========⇒ (2u − 4)|((4u + 4) − (4u − 8)) ⇒
u∈N,u>7
(2u − 4)|12 =====⇒ 2u − 4 = 12 ⇒ u = 8.

5 (a) Arătaţi că dacă p ∈ N, p > 4 este impar, atunci p2 este de forma 4k + 1 (k ∈ N∗ ).
(b) Deduceţi că dacă p ≥ 5, q ≥ 5 sunt ambele numere prime, atunci 24|(p2 − q 2 ).

k=a2 +a∈N∗
Soluţie. (a) p > 4 prim ⇒ p impar, adică ∃a ∈ N∗ astfel ı̂ncât p = 2a + 1 ⇒ p2 = 4a2 + 4a + 1 =======⇒
p2 = 4k + 1.

14
(b) p > 4 prim ⇒ p impar, adică ∃a ∈ N∗ astfel ı̂ncât p = 4a ± 1 ⇒ p2 = 16a2 ± 8a + 1.
q > 4 prim ⇒ q impar, adică ∃b ∈ N∗ astfel ı̂ncât q = 4b ± 1 ⇒ q 2 = 16b2 ± 8b + 1.
.
⇒ p2 − q 2 = (16(a2 − b2 ) + 8(±a ∓ b) .. 8.
p > 4 prim ⇒ p nu este divizibil cu 3 adică ∃c ∈ N∗ astfel ı̂ncât p = 3c ± 1 ⇒ p2 = 9c2 ± 6c + 1.
q > 4 prim ⇒ q nu este divizibil cu 3 adică ∃d ∈ N∗ astfel ı̂ncât q = 3d ± 1 ⇒ q 2 = 9d2 ± 6d + 1.
.
⇒ p2 − q 2 = (9(c2 − d2 ) + 6(±c ∓ d)) .. 3.
(3,8)=1
Am demonstrat că 3|(p2 − q 2 ), 8|(p2 − q 2 ) ====⇒ 24|(p2 − q 2 ).

15
Varianta 6
I 1 Definiţi noţiunea de sistem Peano.

Soluţie. Vezi Curs 1 Definiţia 1

Definiţie. Numim sistem Peano un triplet (N, 0, σ) unde N este o mulţime, 0 ∈ N este un element fixat
al ei şi σ : N → N este o funcţie, astfel ı̂ncât sunt verificate următoarele axiome (Axiomele lui Peano):
P1 0 ∈
/ σ(N) : σ(a) 6= 0, ∀a ∈ N.
P2 funcţia σ este o funcţie injectivă: σ(a) = σ(b) ⇒ a = b.
P3 (Axioma inducţiei): dacă M ⊂ N astfel ı̂ncât
• 0∈M
• m ∈ M ⇒ σ(m) ∈ M
atunci M = N.

2 Dacă a, b ∈ N şi d = (a, b), demonstraţi că există numerele ı̂ntregi u şi v astfel ı̂ncât d = au + bv.

Soluţie. Vezi Curs 5 Teorema 3

Dacă a = b = 0 atunci teorema este adevărată cu u, v arbitrari.
Presupunem că cel puţin unul din cele două numere este nenul, de exemplu b 6= 0. Fie mulţimea

M = {α = ax + by|α ∈ N∗ , x, y ∈ Z} ⊂ N.

Mulţimea M este nevidă, deoarece |a| ∈ M : |a| = a · x + b · 0, cu x = 1 dacă a ≥ 0 şi x = −1 dacă a < 0.
Atunci, conform Principiului Bunei Ordonări, M are un prim element δ = x0 a + y0 b. Vom arăta că δ
verifică cele două condiţii ale Definiţiei celui mai mare divizor comun.
Teorema ı̂mpărţirii cu rest implică faptul că există q, r ∈ Z astfel ı̂ncât a = qδ + r, 0 ≤ r < δ. Atunci
obţinem
r = a − qδ = a − q(x0 a + y0 b) = a(1 − qx0 ) + b(−qy0 ).
Dacă r 6= 0, atunci r ∈ M , ceea ce contrazice minimalitatea lui δ ı̂n M . Deci, r = 0, prin urmare δ|a. În
mod analog obţinem δ|b.
Pe de altă parte, dacă d ∈ Z, d|a şi d|b atunci d|(ax0 + y0 b) = δ, deci δ = (a, b).

3 Enunţaţi Teorema fundamentală a aritmeticii.

Soluţie. Vezi Curs 5 Teoremele 11 şi 12

Teoremă. (Teorema fundamentală a aritmeticii pentru numere naturale) Fie a ∈ N, a > 1. Atunci a
se scrie ı̂n mod unic, până la ordinea factorilor, ca un produs de numere prime.
Teoremă. (Teorema fundamentală a aritmeticii pentru numere ı̂ntregi) Fie a ∈ Z, |a| > 1. Atunci a se
scrie ı̂n mod unic, până la ordinea factorilor şi semnul acestora, ca un produs de numere prime.

4 Enunţaţi şi demonstraţi criteriul de divizibilitate cu 3.

Soluţie. Vezi Cursul 4 Secţiunea 3.1.1

Pn
Teoremă. Numărul a = an an−1 . . . a1 a0 se divide la 3 dacă şi numai dacă suma cifrelor sale i=0 ai se
divide la 3.

16
 .. i · a ... 3 ⇔ (9+1)i =9ki +1 Pn
i · a ... 3 ⇐ .
=======⇒ i=0 (9ki + 1) · ai .. 3 ⇔
Pn Pn
Demonstraţie: a . 3 ⇔ i=0 10 i i=0 (9 + 1) i
Pn ..
i=0 ai . 3.

II 1 Determinaţi toţi divizorii numărului 165.

Soluţie.
165 = 3 × 5 × 11.
Rezultă că divizorii naturali ai lui 165 sunt de forma 3a × 5b × 11c unde a ∈ {0, 1}, b ∈ {0, 1}, c ∈ {0, 1}.
Aceştia sunt:
30 × 50 × 110 = 1,
30 × 50 × 111 = 11,
30 × 51 × 110 = 5,
30 × 51 × 111 = 55,
31 × 50 × 110 = 3,
31 × 50 × 111 = 33,
31 × 51 × 110 = 15,
31 × 51 × 111 = 165.
N = {1, 3, 5, 11, 15, 33, 55, 165}.
Ordonând crescător: D165
Z = {±1, ±3, ±5, ±11, ±15, ±33, ±55, ±165}.
Divizorii ı̂ntregi sunt: D252

2 Determinaţi, folosind algoritmul lui Euclid, cel mai mare divizor comun al numerelor 26 şi 165; scrieţi
cel mai mare divizor comun ca o combinaţie liniară, cu coeficienţi ı̂ntregi, a numerelor 26 şi 165.

Soluţie. Vezi Fişa 5 Exerciţiul 2

165 = 26 × 6 + 9
26 = 9 × 2 + 8
9=8×1+1
Rezultă că cel mai mare divizor comun al numerelor 26 şi 165 este (26, 165) = 1.
Urmărind algoritmul lui Euclid, obţinem 1 = 9 − 8 = (165 − 6 × 26) − (26 − 2 × 9) = 165 − 7 × 26 +
2(165 − 6 × 26) = 3 × 165 − 19 × 26.

3 Demonstraţi, folosind principiul inducţiei matematice, că 5n ≥ 5n, oricare ar fi n ∈ N∗ .

Soluţie. Ne propunem să demonstrăm P (n) : 5n ≥ 5n, ∀n ∈ N.

Pasul I: Etapa de verificare [n = 1]. P (1) : 51 ≥ 5 · 1 este adevărată.
Pasul II: Pasul inductiv [∀k ≥ 1, P (k) ⇒ P (k + 1)]. Presupunem că P (k) este adevărată, adică 5k > 5k.
25k≥5k+5 pentru k≥1
Înmulţind inegalitatea cu 5, rezultă că 5 · 5k ≥ 5 · 5k ⇒ 5k+1 ≥ 25k =============⇒ 5k+1 > 5(k + 1),
deci P (k + 1) este adevărată.
Folosind principiul inducţiei matematice, rezultă că 5n > 5n, ∀n ∈ N∗ .

4 (a) Să se efectueze, ı̂n baza 6, 504(6) + 323(6) .

(b) În ce sistem de numeraţie are loc 123 × 37 = 5015?

17
 Soluţie. (a) Vezi Fişa 3 Exerciţiul 2

4 + 3 = 7 ⇒ 4(6) + 3(6) = 11(6)

0 + 2 + 1 = 3 ⇒ 0(6) + 2(6) + 1(6) = 3(6)
5 + 3 = 8 ⇒ 5(6) + 3(6) = 12(6)
Deci, 504(6) + 323(6) = 1231(6) .
(b) Vezi Fişa 3 Exerciţiul 7
Fie u baza de numeraţie ı̂n care au loc operaţiile. Să observăm, pentru ı̂nceput că u ∈ N, u > 7.
123(u) = u2 + 2u + 3
37(u) = 3u + 7
5015(u) = 5u3 + u + 5
123(u) × 37(u) = (u2 + 2u + 3)(3u + 7) = 3u3 + 13u2 + 23u + 21
123(u) × 37(u) = 5015(u) ⇒ 3u3 + 13u2 + 23u + 21 = 5u3 + u + 5 ⇒ 2u3 − 13u2 − 22u − 16 = 0 ⇒
u natural,u>7
(u − 8)(2u2 + 3u + 2) = 0 ========⇒ u = 8.

5 (a) Să se arate că dacă p ∈ N este un număr prim, p > 4, atunci p este de forma 6k + 1 sau de forma
6k + 5 (k ∈ N∗ ).
(b) Arătaţi că dacă p1 , p2 , . . . pn sunt numere naturale de forma 6k + 5, atunci N = 6p1 p2 . . . pn − 1 are
un divizor prim de forma 6k + 5.

Soluţie. (a) p ∈ N, p > 4 ⇒ p poate fi de forma 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5, k ∈ N∗ .

. . . .
6k..2, (6k+2)..2, (6k+3)..3, (6k+4)..2
Pe de altă parte, p > 4 prim ⇒ p impar şi p nu este divizibil cu 3 ======================⇒ p
este de forma 6k + 1 sau de forma 6k + 5 (k ∈ N∗ ).
(b) N este de forma 6k + 5. Dacă N este prim, problema este demonstrată. Dacă N este compus, fiind
de forma 6k + 5, el nu are ca divizori primi 2 şi 3. Conform punctului anterior, aceştia sunt de forma
6k + 1, 6k + 5. Dacă toţi divizorii primi ar fi de forma 6k + 1, atunci N ar fi de forma 6k + 1 (produsul
a două numere de forma 6k + 1 este de forma 6k + 1), ceea ce nu este adevărat. Deci, N are un
divizor prim de forma 6k + 5.

18