Utente:ValerioPublicola09/sandbox/Teoria dei numeri

Principio di induzione

• Teorema 1 - La somma dei primi numeri interi positivi $n$ è: ${\frac {n(n+1)}{2}}$

• Teorema 2 - Sia $x\in R$ con $x\geqslant 1$, allora: $x^{0}+x^{1}+x^{2}+x^{3}+\dots +x^{n}={\frac {x^{n+1}-1}{x-1}}$

• Corollario 2-1 - Siano $m$ e $n$ due interi positivi e $m>1$, allora $n<m^{n}$

Dimostrazione - Si noti che n volte $1+1+1+\dots +1\leqslant 1+m+m^{2}+m^{3}+\dots +m^{n-1}={\frac {m^{n}-1}{m-1}}$. A sua volta ${\frac {m^{n}-1}{m-1}}<m^{n}-1<m^{n}$ perciò, transitivamente, si ottiene che $n<m^{n}$.

Esempi

• Esercizio 1 - Dimostrare che ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\dots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$.

Per $n=1$ la formula risulta essere vera poiché ${\frac {1}{2\cdot 1}}={\frac {1}{1+1}}$. Supponiamo allora che la formula sia vera per un generico numero $k$. Allora con $k+1$:

${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\dots +{\frac {1}{k(k+1)}}+{\frac {1}{(k+1)(k+1+1)}}=$

$={\frac {k}{k+1}}+{\frac {1}{(k+1)(k+1+1)}}={\frac {k^{2}+2k+1}{(k+1)(k+2)}}={\frac {(k+1)^{2}}{(k+1)(k+2)}}={\frac {(k+1)}{(k+1)+1}}$.

• Esercizio 2 - Dimostrare che $n(n^{2}-1)(3n+2)$ è divisibile per 24.

$24=3\cdot 2^{3}$, quindi è sufficiente dimostrare che l'espressione è divisibile per 3 e per 2³. $n(n^{2}-1)(3n+2)=n(n-1)(n+1)(3n+2)$, tra i tre fattori $n-1,n,n+1$ c'è sicuramente un multiplo di 3 e almeno un multiplo di 2.

1) Supponiamo che $n-1$ sia pari, ossia del tipo $2k$ dove $k\in N_{0}$ ed è dispari, allora $n+1$ si può esprimere come $2k+2=2(k+1)=2\cdot 2a$, dove $a=2k$ (il ragionamento risulta analogo ponendo $k$ pari). Allora, con $n$ dispari, la tesi è confermata poiché $n(n-1)(n+1)(3n+2)=n\cdot 2k\cdot 4a(3(2k+1)+2)=2^{3}ak(3(2k+1)+2)$, quindi è divisibile per 8, e il prodotto $ak$ si può esprimere come $3m$, $m\in N_{0}$, come detto in precedenza: sostituendo, ci si riduce a $2^{3}ak(3n+2)=2^{3}\cdot 3m(3n+2)=24m(3n+2)$.

2) Supponiamo ora che $n$ sia pari, ossia del tipo $2k$ dove $k\in N_{0}$, allora: $n(n-1)(n+1)(3n+2)=2k(2k-1)(2k+1)(3\cdot 2k+2)=2\cdot 2k(2k-1)(2k+1)(3k+1)$. Il fattore 3 è sicuramente compreso nell'espressione, come dimostrato in precedenza, quindi si ragiona sulla divisibilità per 8. Se $k$ fosse pari, ossia esprimibile come $2a$, $2\cdot 2k(2k-1)(2k+1)(3k+1)=4\cdot 2a(4a-1)(4a+1)(6a+1)=8a(4a-1)(4a+1)(6a+1)$, cioè è divisibile per 8. Se $k$ fosse dispari, esprimibile come $2a-1$, si ha che $2\cdot 2(2a-1)(4a-2-1)(4a-2+1)(6a-3+1)=4(2a-1)(4a-3)(4a-1)2\cdot (3a-1)=8(2a-1)(4a-3)(4a-1)$. Anche così l'espressione è divisibile per 24: la tesi è confermata.

Basi

• Teorema 1 - Sia $k$ un intero maggiore di 1, allora per ogni intero $n\in N_{0}$ esiste una rappresentazione:

$n=a_{0}k^{s}+a_{1}k^{s-1}+\dots +a_{s-1}k+a_{s}$

Dove ogni termine $0<a_{i}<k$. In più, ogni intero $n$ ha una e una sola rappresentazione in base $k$.

Esempi

• Esercizio 1 - Dimostrare che ogni intero $n\in N$ è esprimibile come: $\sum _{i=0}^{s}c_{i}3^{i}$ Dove $c_{s}\neq 0$ e $c_{i}$ è uguale a -1, 0 oppure 1.

Ogni numero $n$ è rappresentabile in base 3 come $a_{0}3^{s}+a_{1}3^{s-1}+\dots +3a_{s-1}+a_{s}$ dove $a_{i}$ è un numero tra 2, 1 o 0. Supponiamo che un certo termine della successione sia $2\cdot 3^{k}$, allora si può scrivere come $2\cdot 3^{k}=(3-1)3^{k}=3^{k+1}-3^{k}$, che presenta come coefficiente soltanto 1 e -1. Sostituendo quindi ad ogni $a_{m}=2$, dove $a_{m}$ è coefficiente di $3^{k}$, $a_{m}3^{k}=3^{k+1}-3^{k}$, ogni numero risulta è esprimibile come $\sum _{i=0}^{s}c_{i}3^{i}$.

Divisibilità

• Teorema 1 - (Lemma di Euclide) Per tutti gli interi $k>0$ e j esistono, e sono unici, due interi q e r, dove $0\leqslant r<k$, tali che: $j=qk+r$

• Esercizio 1 - Dimostrare che $MCD(a+b,a-b)\geqslant MCD(a,b)$

Definiamo $a=a_{1}k$ e $b=b_{1}k$, dove $a_{1},b_{1}$ sono coprimi, allora $MCD(a,b)=k$. Quindi $MCD(a+b,a-b)=MCD(a-b,2b)=MCD(a_{1}k-b_{1}k,2b_{1}k)=k$. Quindi, sicuramente, $MCD(a+b,a-b)=k=MCD(a,b)$. Ma può essere anche maggiore se $a$ e $b$ sono, ad esempio, due numeri dispari coprimi. Per dimostrarlo, definiamo $a=2m+1$ e $b=2n+1$, allora $MCD(a,b)=MCD(2m+1,2n+1)=1$; ma: $MCD(2m+1+2n+1,2m+1-2n-1)=MCD(2m+2n+2,2m+2n)=2$. Perciò: $MCD(a+b,a-b)\geqslant MCD(a,b)$

• Teoremi 2 e 3 - (1) Se $m|a$ e $m|b$ allora $m|a+b,a-b,a+kb$. (2) $MCD(a,b)=MCD(a,a+kb)$

Congruenze

[1]

Proprietà

• Proprietà 1 - Se $ar\equiv br{\pmod {m}}\,$ e $MCD(m,r)=d$, allora $a\equiv b{\pmod {m/d}}\,$
• Proprietà 2 - Sia $p(x)$ un polinomio in x con coefficienti interi e $a\equiv b{\pmod {m}}\,$, allora $p(a)\equiv p(b){\pmod {m}}\,$

Esempi

• Esercizio 1 - Dimostra che $(x+y)^{p}\equiv x^{p}+y^{p}{\pmod {p}}\,$, dove $p$ è un numero primo.

Sottintendendo il modulo p, col piccolo teorema di Fermat si ottiene che $(x+y)^{p}\equiv x+y$ e che $x^{p}+y^{p}\equiv x+y$. Per la proprietà transitiva, la congruenza è dimostrata.

• Esercizio 2 - (1) Se $x\equiv m{\pmod {a}}\,$ e $x\equiv m{\pmod {b}}\,$, dimostra che $MCD(a,b)=1$ implica che $x\equiv m{\pmod {ab}}\,$. (2) Cosa succederebbe se $MCD(a,b)=d>1$?

(1) Iniziamo a ragionare con la prima congruenza: $x\equiv m{\pmod {a}}\,$ allora $x-m\equiv 0\equiv a{\pmod {a}}\,$. Con la seconda si ha che $x-m\equiv 0\equiv b{\pmod {b}}\,$; perciò $x-m=abs$, con $s\in N_{0}$. Quindi $x-m\equiv abs\equiv 0{\pmod {ab}}\,$ cioè $x\equiv m{\pmod {ab}}\,$ (2) La dimostrazione precedente è sufficiente per confermare anche la richiesta (2).

• Esercizio 3 - Se $ab\equiv 1{\pmod {m}}\,$ e $bx\equiv c{\pmod {m}}\,$ dimostra che $x\equiv ac{\pmod {m}}\,$.

Moltiplicando la seconda congruenza per $a$, essa rimane vera (poiché sarebbe come aggiungere $a$ volte $bx$ e $c$, che sono congruenti mod m), quindi: $abx\equiv ac{\pmod {m}}\,$. Per la prima congruenza, però, $ab\equiv 1$, allora $abx\equiv x\equiv ac{\pmod {m}}\,$

Equazioni di congruenze

• Teorema 1 - Data la congruenza $ax\equiv b{\pmod {m}}\,$, essa è risolvibile se e solo se $MCD(a,m)=d|b$. Le soluzioni sono del tipo $x=d+t{\frac {m}{d}}$ con $t=\dots ,-2,-1,0,1,2\dots$

Esempi

• Esercizio 1 - Prova che ogni numero primo $p$, diverso da 2 e 5, ha almeno un multiplo in cui tutte le cifre sono 9.

Per il piccolo teorema di Fermat si ha che $a^{p-1}\equiv 1{\pmod {p}}\,$. Poniamo $a=10$, allora $10^{p-1}-1\equiv 0{\pmod {p}}\,$, dove $10^{p-1}-1$ è chiaramente un numero, multiplo di $p$ (perché congruo a 0 mod p), formato da tutte cifre 9. Anche se il problema non lo richiede, si possono trovare infiniti numeri formati da tutti 9 e multipli di $p$ semplicemente ponendo $a=10,10^{2},10^{3},10^{4}\dots$ con la condizione $p\neq 2,5$ poiché la congruenza $a^{p-1}\equiv 1{\pmod {p}}\,$, a differenza di $a^{p}\equiv a{\pmod {p}}\,$, è vera se e solo se $a$ e $p$ sono coprimi.

Funzione di Eulero e proprietà

• Teorema 1 - Sia l'$MCD(a,n)=1$ allora $a^{\varphi (n)}\equiv 1{\pmod {n}}\,$

• Proprietà di φ - Sia l'$MCD(a,n)=1$ allora $\varphi (ab)=\varphi (a)\varphi (b)$

• Teorema 2 - Se $a$ e $m$ sono coprimi, sia $r$ il minor esponente tale per cui $a^{r}\equiv 1{\pmod {m}}\,$ e sia $s>r$ tale per cui $a^{s}\equiv 1{\pmod {m}}\,$ allora $r|s$.

Equazioni diofantee

[2] [3]

Bibliografia

• George Andrews, Number Theory, 1974. p. 61
• Vinogravod, Elements on number theory, 1954.