Divisibilità

In decimale $a\in \mathbb{N}$ si può rappresentare come la somma delle sue cifre: $$a=c_0+10c_1+10^2{c}_2+...+10^n{c}_n=c_0+\sum _{i=1}^n{c}_{i}10^i$$

Quindi per stabilire se $b|a$, cioè se $a$ è multiplo di $b$, basta verificare che: $$a{\equiv }_{b}0\iff c_0+\sum _{i=1}^n{c}_i(10^i\mathrm{mod}b){\equiv }_{b}0$$

Di conseguenza se ne può ricavare che:

• $$2|a\iff c_0{\equiv }_{2}0$$ cioè quando l'ultima cifra è pari, perchè $10^i{\equiv }_{2}0,\forall i\ge 1$.

• $$3|a\iff \sum _{i=0}^n{c}_i{\equiv }_{3}0$$ cioè quando la somma delle cifre è multiplo di $3$, perchè $10^i{\equiv }_{3}1,\forall i\ge 1$.

• $$4|a\iff c_0+2c_1{\equiv }_{4}0$$ perchè $10^1{\equiv }_{4}2$ mentre $10^i{\equiv }_{4}0,\forall i\ge 2$.

• $$5|a\iff c_0{\equiv }_{5}0$$ cioè quando l'ultima cifra è $0$ o $5$, perchè $10^i{\equiv }_{5}0$.

• $$6|a\iff 3|a\wedge 2|a$$ e quindi la somma delle cifre è multiplo di $3$ e l'ultima è pari.

e per estensione:

• $$8|a\iff c_0+2c_1+4c_2{\equiv }_{8}0$$ perchè $10^1{\equiv }_{8}2$, $10^2{\equiv }_{8}4$ mentre $10^i{\equiv }_{8}0,\forall i\ge 3$.

• $$9|a\iff \sum _{i=0}^n{c}_i{\equiv }_{9}0$$ cioè quando la somma delle cifre è multiplo di $9$, perchè $10^i{\equiv }_{9}1,\forall i\ge 1$.

• $$10|a\iff c_0{\equiv }_{10}0$$ cioè quando l'ultima cifra è $0$, perchè $10^i{\equiv }_{10}0$.

In questo modo è possibile semplificare il calcolo del resto, per esempio $12530\cdot 114211{\equiv }_{3}2\cdot 1{\equiv }_{3}2$, perchè $1+2+5+3+0=11{\equiv }_{3}2$ e $1+1+4+2+1+1=10{\equiv }_{3}1$.

Minimo comune multiplo

Dati $a,b\in \mathbb{Z}$ il minimo fra i multipli comuni di $a$ e $b$ è detto minimo comune multiplo, ed è il numero più piccolo che è multiplo di entrambi: $$\mathrm{mcm}(a,b)$$

Massimo comun divisore

Dati $a,b\in \mathbb{Z}$ il massimo fra i divisori comuni di $a$ e $b$ è detto massimo comun divisore, ed è il numero più grande che divide entrambi: $$\mathrm{MCD}(a,b)$$

Quando $MCD(a,b)=1$, $a$ e $b$ si dicono relativamente primi o anche coprimi.

Algoritmo di Euclide

Siano $a,b\in \mathbb{N}$, la procedura sarà:

int gcd(int a, int b) {
	if (b > a) {
		swap(&a, &b);
	}

	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}

	return a;
}

che espressa ricorsivamente diventa: $$\mathrm{MCD}(a,b)=\{\begin{array}{ll}a& \text{se }b=0\\ \mathrm{MCD}(b,a\mathrm{mod}b)& \text{se }b>0\end{array}$$

Per esempio, se $a=300$ e $b=18$:

1. $a=18$, $b=300\mathrm{mod}18=12$
2. $a=12$, $b=18\mathrm{mod}12=6$
3. $a=6$, $b=12\mathrm{mod}6=0$

e quindi $\mathrm{MCD}(300,18)=6$.

Identità di Bezout

Siano $a,b\in {\mathbb{N}}^{+}$, allora: $$\exists x,y\in \mathbb{Z}:\mathrm{MCD}(a,b)=ax+by$$

Per esempio, $\mathrm{MCD}(12,8)=4$ allora $4=12\cdot 1+8\cdot (-1)$.

L'identità è possibile generalizzarla, infatti con $a,b,c\in \mathbb{Z}$: $$\exists x,y:ax+by=c\iff \mathrm{MCD}(a,b)|c$$ e cioè che esistono soluzioni solamente se $c$ è divisbile per il massimo comun divisore.

Per esempio, l'equazione $240x+36y=24$:

1. Ha soluzioni perchè $\mathrm{MCD}(240,36)=12$ e $12|24$
2. Dividendo per $12$ si ha che $20x+3y=2$, dove $20$ e $3$ sono coprimi, infatti $\mathrm{MCD}(20,3)=1$
3. Essendo coprimi $\exists z,w\in \mathbb{Z}:20z+3w=1$ per l'identità di Bezout, per cui $x=2z$ e $y=2w$, dato che $20\cdot 2z+3\cdot 2w=2$
4. Di conseguenza basta trovare $z$ e $w$, che saranno $z=-1$ e $w=7$
5. Quindi $x=-2$ e $y=14$ è una possibile soluzione

Proprietà di cancellazione

Siano $a,b,c\in \mathbb{Z}$ e $n\in \mathbb{N}$, allora: $$ac{\equiv }_{n}bc\Rightarrow a{\equiv }_{n}b\iff \mathrm{MCD}(c,n)=1$$