Divisibilitas

Divisibilitas est verum initium theoriae numerorum, quia numeros integros in systema structura praeditum convertit: iam non spectas numeros ut “quantitates”, sed ut partes quae inter se congruunt aut non congruunt. Una sola structura, a\mid b, sinit te exprimere tam criteria simplificationis et factorizationis quam ipsum cor quorumdam processuum, ut algorithmus Euclidis, qui efficit ut maximi communes divisores etiam numerorum magnorum intra paucos gradus computari possint. Praeterea, haec est basis technica notionum quae iterum atque iterum apparent in mathematica applicata et computatione: congruentiae, arithmetica modularis, validationes, codices, et (postea) cryptographia. Divisibilitatem dominari est, essentia tenus, discere rationes occultas in numeris integris deprehendere atque eas in processus convertere qui semper operantur.

Proposita Discendi
Ad finem huius apuncti discipulus poterit:

1. Intellegere relationem divisibilitatis inter numeros integros.
2. Intellegere definitionem divisibilitatis et eius proprietates.
3. Elaborare demonstrationes mathematicas de effectibus et theorematibus ad divisibilitatem pertinentibus.

INDEX CONTENTORUM
Definitio divisibilitatis
Proprietates fundamentales divisibilitatis
Exercitationes Propositae

Definitio divisibilitatis

Notio informalis “a dividit b” fit precisa cum eam ut relationem inter numeros integros exprimimus. Dicemus numerum integrum a dividere numerum integrum b, si b scribi potest ut multiplex exactum ipsius a. Haec definitio est fundamentum reliqui apuncti, quia locutiones huius modi “exacte convenit” in criterium verificabile convertit.

Definitio. Sint a,b\in\mathbb{Z} cum a\neq 0. Dicimus a dividere b, et scribimus a\mid b, si et solum si existit numerus integer k\in\mathbb{Z} talis ut b=ka. Aliter, scribimus a\nmid b.

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

In hac definitione, numerus k vocatur quotiens (vel factor) divisibilitati associatus. Exempli gratia, affirmare 6\mid 42 aequivalet affirmare existere k\in\mathbb{Z} tale ut 42=6k; hoc in casu, satis est sumere k=7.

Magni momenti est considerare

• Conditio a\neq 0 est essentialis. Nam si conaremur admittere a=0, condicio divisibilitatis postularet existere k\in\mathbb{Z} tale ut b=0\cdot k. Sed 0\cdot k=0 pro omni k, ita ut sola possibilitas esset b=0. In eo casu, nullus esset k a relatione “determinatus”, quippe cum quilibet k\in\mathbb{Z} conditionem 0=0\cdot k satisfaciat. Aliter dictum, expressio informalis k=b/a fit k=0/0, quae definita non est. Ad hanc degenerationem vitandam (ubi notio quotiens significationem amittit), requiritur a\neq 0. Hac de causa relatio 0\mid b valida non habetur.
• Contra, a\mid 0 verum est pro omni a\in\mathbb{Z} cum a\neq 0, quia satis est sumere k=0 et impletur 0=a\cdot 0.

Ex hac definitione sequitur aequivalentia qua frequenter utemur: dicere a\mid b idem est ac dicere b ad pertinere ad multitudinem multiplorum integrorum ipsius a, id est b\in a\mathbb{Z}, ubi a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}. Haec scribendi ratio extollit divisibilitatem non esse “artificium”, sed modum describendi subcollectiones valde structas intra \mathbb{Z}.

Proprietates fundamentales divisibilitatis

• Reflexivitas: a\mid a.
  Demonstratio:

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Neutrum multiplicativum in $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Introductio existentialis (1)}\\ (3) &\vdash a \mid a &\text{; Definitio divisibilitatis (2)} \\ &\blacksquare & \end{array}

• Transitivitas: si a\mid b et b\mid c, tunc a\mid c.

  Demonstratio:

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Def. divisibilitatis, Praesumptio}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Def. divisibilitatis, Praesumptio}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-Compactatio(1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; Ex(3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; Ex(4)}\\ &\text{Algebra intra quantificatorem}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; Ex(5)}\\ &\text{Clausura $\mathbb{Z}$ sub multiplicatione}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Def. divisibilitatis (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD(7)}\\ &\blacksquare& \end{array}

• Compatibilitas cum additione et subtractione: si a\mid b et a\mid c, tunc a\mid (b+c) et a\mid (b-c).
  Demonstratio:

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Def. divisibilitatis, Praesumptio}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Def. divisibilitatis, Praesumptio}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-Compactatio(1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; Ex(3)}\\ &\text{Algebra intra quantificatorem.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; Ex(4)}\\ &\text{Clausura $\mathbb{Z}$ sub additione.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Def. divisibilitatis (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD(6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; Ex(3)}\\ &\text{Algebra intra quantificatorem.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; Ex(8)}\\ &\text{Clausura $\mathbb{Z}$ sub subtractione.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Def. divisibilitatis (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD(10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{;$\wedge$-Introductio in consequenti(7,11) }\\ &\blacksquare& \end{array}

• Compatibilitas cum productis: si a\mid b, tunc a\mid (bc) pro omni c\in\mathbb{Z}.
  Demonstratio:

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Def. divisibilitatis, Praesumptio}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; Ex(1), $\forall$-Introductio (c arbitrarium)}\\ &\text{Algebra in }\mathbb{Z}\text{ intra quantificatorem existentiel.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; Ex(2), clausura: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Def. divisibilitatis (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD(4)}\\ &\blacksquare& \end{array}

Theorema: cota divisorii

Si b\neq 0 et a\mid b, tunc |a|\le |b|.

Demonstratio:

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Praesumptio} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Def. divisibilitatis, Praesumptio} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Prop. valoris absoluti, Ex(2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; Ex(1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; Ex(4), si }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; Ex(5)} \\ &\blacksquare& \end{array}

Exercitationes Propositae

1. Ostende theorema “cota divisorii” non necessario verum esse si b=0.
2. Consideremus collectionem A et relationem \rho super hanc collectionem. Si elementa x,y\in A ita se habeant ut x ad y per \rho referatur, tunc scribitur x\rho y. Relatio \rho dicitur esse ordinis partialis super A si:

   a)(\forall x\in A) (x\rho x),
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).

   Demonstra relationem divisibilitatis esse relationem ordinis partialis super numeros integros.

3. Proba per inductionem quod, si a\mid b_1, a\mid b_2, \cdots, a\mid b_n, tunc a\mid \sum_{i=1}^n b_i x_i pro quolibet coetu \{x_i\}_{i=1}^n \subset \mathbb{Z}. Praeterea ostende quod, si a\mid b_i, cum i\in \{1,2,3,\cdots, n\}, et c scribi potest ut combinatio linearis horum b_i, tunc a\mid c.
4. Si a\neq 0, ostende collectionem \{x\;:\; d\mid a\} finitam esse.
5. Considera n\in\mathbb{Z}^+ fixum, et sit

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   Proba:

   1. d\in S \leftrightarrow n/d\in S
   2. Si elementa S ordine crescente disponuntur: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n, tunc elementa correspondentia n\mid d_i cum i \in \{1,2,\cdots, t\} ordine decrescente sunt.
6. Suppone a,b\in\mathbb{Z}^+ et ab=c. Demonstra \min\{a,b\}\le \sqrt{c}.
7. Integer n dicitur par si 2\mid n, et impar si 2\nmid n. Demonstra summam et differentiam:
   1. duorum parium esse numerum parem.
   2. duorum imparium esse numerum parem.
   3. pari et impari esse numerum imparem.
8. Si n est impar a \pm 1 distinctus, proba n duos pares consecutivos dividere non posse.
9. Sint a,b,n\in\mathbb{Z} tales ut |a-b|\lt |n|. Proba n neque a neque b dividere posse.
10. Suppone a\in\mathbb{Z}. Proba:
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. Sint a,b,c\in\mathbb{Z} et supponamus c\neq 0. Ostende ac\mid bc implicare a\mid b.