Esercizi di Teoria Elementare dei Numeri (III)

Esercizio 1

I numeri di Fermat sono così definiti: \(F_{n}=2^{2^{n}}+1\). Dimostrare che tutti i numeri di Fermat con \( n>1\) hanno l’ultima cifra uguale a \(7\).

Suggerimento
Il numero \(2^{2^{2}}=16\) termina con la cifra \(6\). Lo stesso vale quindi per i numeri \(2^{2^{n}}\) con \(n > 2\).
Per le proprietà dei numeri di Fermat vedere l’articolo su questo blog.

Esercizio 2

Dimostrare che condizione necessaria affinché un numero della forma \(n^{n}+1\) sia primo è che \(n=2^{2^{r}}\).

Suggerimento
Supponiamo \(n=2^{t}m\) dove \(m\) è dispari. Se fosse \(m >1\) allora \((n^{2^{t}})^{m}+1\) sarebbe composto, a causa della seguente formula:

\[ a^{2k+1}+b^{2k+1} = (a+b)(a^{2k}-a^{2k-1}b+ \cdots -ab^{2k-1}+b^{2k}) \]

Se \(t=0\) abbiamo finito. Se \(t>0\) allora \(t=2^{r}s\), dove \(s\) è dispari. Ragionando come sopra dedurre che deve essere \(s=1\).

Esercizio 3

Dimostrare la seguente identità:

\[ (1-\frac{1}{2^2})(1-\frac{1}{3^2}) \cdots (1-\frac{1}{n^2})=\frac{n+1}{2n} \]

Esercizio 4

Dimostrare la seguente formula:

\[ 2 \cos \left(\frac{\pi}{2^{n+1}}\right)=\sqrt{2+\sqrt{2+ \cdots \sqrt{2}}} \]

dove il numero delle radici quadrate è uguale a \(n\).

Esercizio 5

Dimostrare che se un intero \(n\) è della forma \(n=4k+3, k \in \mathbb{N}\), allora \(n\) ha almeno un fattore primo della stessa forma.

Suggerimento
I numeri primi dispari sono tutti della forma \(4k+1\) oppure \(4k+3\). Notare inoltre che il prodotto di due numeri della forma \(4k+1\) è anch’esso della stessa forma.

Esercizio 6

Dimostrare che se \(n\) è un intero positivo dispari allora:

\[ \binom{n}{1}-5\binom{n}{2}+5^{2}\binom{n}{3}- \cdots + 5^{n-1}\binom{n}{n} = \frac{1}{5}(1+4^{n}) \]

Esercizio 7

Dimostrare che l’ultima cifra diversa da zero di \(n!\) è sempre pari, se \(n \ge 2\).

Suggerimento
Possiamo scrivere \(n! = 2^{r}5^{s}m\), dove \((m,10)=1\). Quindi riflettere sul fato che deve essere sempre \(r > s\).
Come conseguenza ulteriore possiamo affermare che la massima potenza di \(10\) che divide \(n!\) è \(10^{s}\).

Esercizio 8

Sia \(d(n)\) la funzione aritmetica che conta il numero dei divisori positivi di \(n\). Dimostrare la seguente formula:

\[ \sum_{k|n}d^{3}(k)=\left(\sum_{k|n}d(k)\right)^{2} \]

Per le proprietà della funzione \(d(n)\) vedere sempre l’articolo di questo blog menzionato nel primo esercizio. Vedere anche l’articolo riguardante le funzioni aritmetiche e in particolare il prodotto di Dirichlet.

Suggerimento
Dimostrare prima che entrambe le funzioni a destra e sinistra sono moltiplicative. Quindi dimostrare la formula per il caso \(n=p^{a}\). Ricordare inoltre la seguente formula:

\[ \sum_{k=1}^{n}k^{3}=(1+2+ \cdots + n)^{2} \]

Esercizio 9

Dimostrare che un numero intero della forma \(4k+3\) non può essere somma di due quadrati.

Suggerimento
Il quadrato di un intero è congruente a \(0\) oppure a \(1\) modulo \(4\).

Esercizio 10 – Eulero

Dimostrare che il numero di Fermat \(F_{5}=2^{2^{5}}+1\) è divisibile per \(641\).

Suggerimento
Utilizzare la relazione \(5\cdot 2^{7} \equiv -1 \pmod{641}\). Elevare alla quarta potenza e notare che \(5^{4} \equiv -16 \pmod{641}\).
I numeri di Fermat \(F_{0}=3,F_{1}=5,F_{2}=17,F_{3}=257,F_{4}=65537\) sono primi. Fermat nel 1650 fece la congettura che tutti i numeri di Fermat sono primi. Tuttavia ad oggi non sono stati trovati numeri di Fermat primi per \(n \ge 5\). Quelli calcolati sono tutti composti.