Esercizi di Teoria Elementare dei Numeri (II)

Esercizio 1

Sia \(x_{1}=2\)  e \(x_{n+1}= x_{n}^{2} – x_{n}+1\). Dimostrare che i numeri \(x_{n}\) sono primi fra loro.

Soluzione
I valori della successione si ottengono iterando il polinomio \(P(x)=x^{2}-x+1\). Ragionando per induzione si può vedere facilmente che dato \(m <n\) risulta la seguente relazione:

\[ x_{n}= x_{m}Q(x_{m}) +1 \]

dove \(Q(x)\) è un polinomio a coefficienti interi. Quindi \((x_{n},x_{m})=1\) in quanto un fattore comune a \(x_{n}\) e \(x_{m}\) dovrebbe dividere il numero \(1\).

Esercizio 2

Sia p un numero primo dispari. Dimostrare che il numeratore del seguente numero razionale

\[ 1 + \frac{1}{2} + \frac{1}{3}+ \cdots + \frac{1}{p-1} \]

è divisibile per p.

Esercizio 3

Sia p un numero primo dispari maggiore di \(3\). Dimostrare che il numeratore del seguente numero razionale

\[ 1 + \frac{1}{2} + \frac{1}{3}+ \cdots + \frac{1}{p-1} \]

è divisibile per \(p^{2}\).

Esercizio 4

Sia \(\{p_{1},p_{2}, \cdots p_{n}, \cdots \}\) la successione ordinata dei numeri primi. Dimostrare che

\[ p_{n+1} \le p_{1}p_{2} \cdots p_{n} +1 \]

Esercizio 5

Dimostrare che per ogni intero positivo \(N\), esiste un numero primo la cui somma delle cifre decimali è maggiore di \(N\).

Per questo esercizio ricordiamo il seguente importante Teorema di Dirichlet: ogni progressione aritmetica \(\{an+b, n=1,2,…\}\) con \((a,b)=1\) contiene infiniti numeri primi.
Per una dimostrazione vedere ad esempio ^[1] (disponibile su Amazon.com).

Traccia soluzione
Fissato \(N >0\) abbiamo \((10^{N},10^{N}-1)=1\). Quindi applicare il teorema di Dirichlet che assicura l’esistenza di un numero primo \(p=10^{N}n + 10^{N}-1\). Notare che le \(N\) cifre del numero \(10^{N}-1\) sono tutte uguali a \(9\) e quindi concludere la dimostrazione.

Esercizio 6

Provare che le ultime quattro cifre dei numeri \(\{5^{n} , n=1,2,3…\}\) formano una successione periodica. Trovare il periodo.

Soluzione
I primi valori della successione sono i seguenti: \(\{5,25,125,625,3125,15625,78125,390625,1953125\}\).
Notiamo che \(5^{n+4} -5^{n} \equiv 0 \pmod {10000}\) se \(n \ge 4\), in quanto \(5^{4} \cdot (5^{4}-1)=390000\); quindi le ultime 4 cifre formano un periodo di lunghezza 4. Il periodo è costituito dai numeri \(\{0625,3125,5625,8125\}\).

Esercizio 7

Trovare tutti gli interi \((m,n)\) tali che \(m^{4} + 4n^{4}\) è un numero primo.

Traccia
Utilizzare la seguente relazione:

\[ m^{4} + 4n^{4}=[(m+n)^{2}+n^{2}][(m-n)^{2}+n^{2}] \]

Quindi dedurre che deve essere \([(m-n)^{2}+n^{2}]=1\), e concludere.

Risposta: [m=n=1]

Esercizio 8

La funzione di Eulero \(f(x)= x^{2}+x+41\) assume tutti valori primi per \(x=0,1,2, \cdots 39\), come si può verificare. Dimostrare, senza effettuare calcoli, che assume valori primi anche nei numeri negativi \(x=-1,-2, \cdots -40\).

Esercizio 9

Dimostrare la seguente relazione:

\[ 0 \le \Bigl \lfloor x \Bigr \rfloor – 2 \left \lfloor \frac{x}{2} \right \rfloor \le 1 \]

In altri termini l’espressione \(\left \lfloor x \right \rfloor – 2 \left \lfloor \frac{x}{2} \right \rfloor\) assume solo i valori \(0\) e \(1\).

Esercizio 10

Sia \(\{p_{1},p_{2}, \cdots p_{n}, \cdots \}\) la successione ordinata dei numeri primi. Dimostrare la seguente disuguaglianza:

\[ p_{n} < 2^{2^{n}} \]

Suggerimento
Utilizzare l’esercizio 4 e procedere per induzione.

---

Bibliografia

^[1]T. Apostol – Introduction to Analytic Number Theory (Springer-Verlag)