Divizibilitate - Noţiuni generale şi importante

[Admin]

Fie că se discută de divizibilitatea în N sau în Z acestea vor fi principalele "cadre" de discuţie.
Topicul poate conţine şi divizibilităţi legate de noţiunile mai generale de divizibilitate.

Indiferent de "cadrul" de discuţie (N, Z, ...) a spune că b | a (citim : b divide pe a) înseamnă prin definiţie că există un număr c astfel încât a = bc .
(În acest caz am presupus că operaţia de înmulţire este comutativă, adică aşa cum este cazul în N, Z, ...etc)

[Admin]

Problemă extrem de importantă

Dacă a şi b sunt două numere întregi (deci din Z) iar d = (a,b)
atunci există k, n două numere întregi astfel încât :

ak + bn = d

Demonstraţie :

### Dacă ambele numere a şi b sunt nule (a=b=0) atunci este evident că putem lua orice întregi k, n şi avem :
ak+bn = 0 = (a,b) . (Vezi observaţia din postarea precedentă, fiindcă se consideră (0,0) = 0)
Presupunem acum că măcar unul dintre a şi b este nenul.

### Considerăm mulţimea S formată din toate elementele de forma ax+by , unde x şi y sunt numere întregi.

### Dacă ax+by < 0 atunci a(-x)+b(-y) > 0 (şi reciproc), deci mulţimea S conţine atât numere pozitive cât şi negative.

### Fie mulţimea P care conţine toate numerele STRICT POZITIVE din mulţimea S .
Deci cu siguranţă avem în P un CEL MAI MIC ELEMENT. Fie acesta d . (Vom arăta că d este chiar (a,b) ...)

### Deci există k, n întregi astfel încât ak+bn = d (***)
Evident (a,b) | d din relaţia de mai sus (.. se scoate (a,b) în factor comun, etc)

### Rămâne de arătat că d | a şi d | b
Presupunem prin absurd că d nu îl divide pe a.
Atunci, din Teorema împărţirii cu rest (care funcţionează evident şi în Z) avem, prin împărţirea lui a la d :
a = dq + r , unde 0 < r < d

Atunci, fiindcă ak+bn = d, avem :

0 < r = a - dq = a - (ak+bn)q = a (1-kq) + b (-nq)

... deci am obţinut un număr întreg strict pozitiv r, mai mic decât d şi care este de forma ax+by , deci NU ESTE d cel mai mic element din mulţimea P. Contradicţie !!! (Analog dacă d nu îl divide pe b).

### Deci într-adevăr d (adică cel mai mic element din mulţimea P) este (a,b) şi scrierea din (***) spune ak+bn = d.

---

OBSERVAŢIE : Scrierea NU este unică.

Adică, dacă avem (a,b) = d şi avem o scriere ak + bn = d atunci e suficient să observăm că :
a(k-b) + b (n+a) = ak - ab + bn + ba = ak + bn = d

[Admin]

OBSERVAŢIE

Dacă d | a şi d | b iar ak + bn = d atunci (a,b) = d

Demonstraţie:

În relaţia ak + bn = d iese în membrul stâng în factor (a,b) care va divide pe d, deci (a,b) = d .

[Admin]

FORMULA LUI GAUSS

$$\sum_{d|n} \varphi {(d)} = n$$

Demonstraţie :

În postarea precedentă am făcut observaţia evidentă :

OBSERVAŢIE

Dacă d | a şi d | b iar ak + bn = d atunci (a,b) = d

Demonstraţie:

În relaţia ak + bn = d iese în membrul stâng în factor (a,b) care va divide pe d, deci (a,b) = d .

Considerăm mulţimea cadru de lucru M = {1,2,...,n} şi fie d | n (... cu d în mulţimea cadru M).

Mulţimea multiplilor lui d în mulţimea M este : 1*d, 2*d, ... , (n/d)*d (***)

Fie d|n (deci d este divizor al lui n).
ÎNTREBARE : Câţi multipli ai lui d din M, notaţi cu z, au proprietatea (z/d, n/d) = 1 ? (deci z/d şi n/d prime între ele)
(Spunem pentru uşurinţa demonstraţiei că z satisface proprietatea P )
RĂSPUNS : Sunt evident $\varphi {(n/d)}$
OBSERVAŢIE : Este vorba exact de tot atâtea numere naturale mai mici sau egale decât n/d şi prime cu n/d .
Atunci vom putea SELECTA / ALEGE în lista (***) cele $\varphi {(n/d)}$ numere obţinute din cele $\varphi {(n/d)}$ numere naturale mai mici decât n/d şi prime cu n/d pe care le înmulţim cu d.

DEMONSTRAŢIA propriu-zisă :

Vom scrie în ordine crescătoare mulţimea divizorilor lui n, enumerând apoi mulţimea multiplilor acestora (totul în M)

# 1 »»» 1*1, 2*1, ... , (n/1)*1 »»» Sunt $\varphi {(n/1)}$ numere $\leqslant$ n/1 şi prime cu n/1 »»»
»»» Selectăm cele $\varphi {(n/1)}$ elemente corespunzătoare (au proprietatea P) din lista de mai sus a multiplilor lui 1 .
....................

# d »»» 1*d, 2*d, ... , (n/d)*d »»» Sunt $\varphi {(n/d)}$ numere $\leqslant$ n/d şi prime cu n/d »»»
»»» Selectăm cele $\varphi {(n/d)}$ elemente corespunzătoare din lista de mai sus a multiplilor lui d .
....................

# n »»» 1*n »»» Sunt $\varphi {(n/n)}$ numere $\leqslant$ n/n şi prime cu n/n (Observaţie : prin definiţie $\varphi {(1)} = 1$) »»»
»»» Selectăm cele $\varphi {(n/n)}$ elemente corespunzătoare din lista de mai sus a multiplilor lui n .

---

Pasul 1. Arătăm că nu am ales de 2 ori acelaşi element.
Fie d si d' doi divizori ai lui n. Dacă avem :

d | z astfel încât (z/d, n/d) = 1 »»» avem o scriere h*(z/d) + k*(n/d) = 1
d' | z astfel încât (z/d', n/d') = 1 »»» avem o scriere h' *(z/d') + k' *(n/d') = 1 . Acestea echivalează cu :

hz + kn = d
h'z + k'n = d'

Deoarece d este divizor al lui z şi al lui n atunci d | h'z + k'n = d' adică d | d'. Analog d' | d. Deci d = d' .

Pasul 2. Pentru un număr z din mulţimea cadru M = {1,2,...,n}, presupunând (z,n) = d atunci z va fi ales în momentul enumerării divizorului d (în scrierea în ordine crescătoare a divizorilor lui n).
Cu alte cuvinte am ales o singură dată fiecare element din mulţimea M = {1,2,...,n}, care are evident n elemente.
Şi la fiecare pas, pentru un divizor d, am ales $\varphi {(n/d)}$ elemente.

Finalizare :
Dacă d parcurge în ordine crescătoare lista divizorilor lui n, atunci n/d parcurge aceeaşi listă în ordine descrescătoare.
Atunci : $$\sum_{d|n} \varphi {(d)} = \sum_{d|n} \varphi {(n/d)} = n$$

[Admin]

OBSERVAŢIE la demonstraţia Formulei lui GAUSS

Fie n număr natural nenul.

Se cunoaşte notaţia clasică [n] = {1,2,...,n} (adică notaţia pentru mulţimea cadru de lucru M = {1,2,...,n} de mai sus)
Deseori vom folosi notaţia clasică [n] = {1,2,...,n} pentru a nu mai implica multe litere.

Din demonstraţia de mai sus se desprinde clar o partiţionare (PARTIŢIE) a mulţimii [n] = {1,2,...,n}.
Adică o reuniune de (sub)mulţimi NEVIDE, DISJUNCTE şi a căror reuniune este întreaga mulţime [n] = {1,2,...,n}

Anume, pentru d | n vom avea clasa (submulţimea de numere din [n] = {1,2,...,n}) notată C_d şi formată astfel :

C_d = {z ∈ N | d | z şi (z/d,n/d) = 1 }

### Evident d ∈ C_d deci mulţimile sunt nevide

### Conform demonstraţiei de la Pasul 1 din postarea precedentă mulţimile C_d sunt disjuncte

### Conform demonstraţiei de la Pasul 2 din postarea precedentă fiecare element :

z ∈ [n] se regăseşte în C_(z,n) deci reuniunea claselor C_d este [n]
şi cum cardinalul claselor este |C_d| = φ(n/d)

... obţinem formula lui GAUSS :
$$\sum_{d|n} \varphi {(d)} = n$$

[Admin]

OBSERVAŢIE utilă în demonstrarea unor probleme la care nu se observă uşor cu ce elemente se poate lucra efectiv.

Două numere naturale nenule d şi d' sunt DIFERITE dacă şi numai dacă există p prim şi s natural nenul astfel încât :

p^s | d dar p^s nu divide pe d' (.. sau invers p^s | d' dar p^s nu divide pe d ..)

DEMONSTRAŢIE :

- Demonstraţia este evidentă dacă în descompunerile în factori primi ale lui d şi d' nu apar aceeaşi factori primi.

- Dacă în descompuneri apar aceeaşi factori primi .
Deoarece d ≠ d' atunci trebuie să existe un factor prim la care exponenţii diferă, luăm p acel factor prim iar s va fi cel mai mare dintre cei 2 exponenţi ai lui p din descompunerile lui d şi d' .

---

Folosind această observaţie se poate demonstra ceea ce este la "Pasul 1" din demonstraţia Formulei lui Gauss (două postări mai sus) - o demonstraţie mai puţin elegantă, e adevărat, dar care pune în evidenţă ŞI alte lucruri aspecte