In questo articolo presentiamo alcuni esercizi della teoria elementare dei numeri, che non richiedono conoscenze matematiche avanzate. Seguiranno altri articoli con esercizi collegati ai vari settori di questa affascinante branca della matematica.
Ricordiamo che il simbolo \(\left\lfloor x \right\rfloor\) indica la parte intera del numero reale \(x\), cioè il più grande intero che è minore od uguale a \(x\). Ad esempio \(\lfloor \frac{30}{7} \rfloor=4\), \(\lfloor -\frac{10}{3} \rfloor=-4\). Le seguenti proprietà seguono facilmente dalla definizione ( \(x\) numero reale, \(n\) intero):

\[ \begin{split} \lfloor x+n \rfloor &= \lfloor x \rfloor + n \\ \left\lfloor \frac{x}{n} \right\rfloor &= \left\lfloor \frac{\left\lfloor x \right\rfloor}{n} \right\rfloor \text { se \(n \ge 1\)} \end{split} \]

Esercizio 1

Dato un intero positivo \(n \ge 1\). Dimostrare che il numero delle cifre nella rappresentazione decimale è \((\lfloor \log_{10}(n) \rfloor + 1)\).

Esercizio 2

Dato un numero reale \(x\) e un intero positivo \(n\) dimostrare la seguente formula:

\[ \left\lfloor {x} \right\rfloor + \left\lfloor {x + \frac{1}{n}} \right\rfloor + \left\lfloor {x + \frac{2}{n}} \right\rfloor + \cdots + \left\lfloor {x + \frac{n-1}{n}} \right\rfloor – \left\lfloor {nx} \right\rfloor = 0 \]

Suggerimento
Indichiamo con \(F(x)\) l’espressione a sinistra. In primo luogo notiamo che \(F(x)=0\) per ogni \( x \in [0,\frac{1}{n})\). Quindi dimostrare che \(F(x + \frac{1}{n})= F(x)\).

Esercizio 3

Dimostrare le seguenti proprietà:

\[ \begin{split} 2^{n} &\equiv 1 \pmod{3} \text { se n è pari} \\ 2^{n} &\equiv 2 \pmod{3} \text { se n è dispari} \\ \end{split} \]

Suggerimento
Ricordare la seguente proprietà delle congruenze: se \(a \equiv b \pmod {n}\) e \(c \equiv d \pmod {n}\), allora \( ac \equiv bd \pmod{n}\).

Esercizio 4

Calcolare la seguente somma:

\[ S =\left\lfloor {\frac{1}{3}} \right\rfloor + \left\lfloor {\frac{2^{1}}{3}} \right\rfloor + \left\lfloor {\frac{2^{2}}{3} } \right\rfloor + \cdots + \left\lfloor {\frac{2^{100}}{3}} \right\rfloor \]

Suggerimento
Utilizzare l’esercizio 3. Ricordare inoltre la formula della somma della progressione geometrica:

\[ \sum_{i=0}^{n}{x^{i}} = \frac{x^{n+1}-1}{x-1} \]

Soluzione: [\(S=\frac{1}{3}(2^{101}-2)-50\)]

Esercizio 5

Siano \(n,m\) interi non negativi. Dimostrare che la seguente espressione è sempre un intero:

\[ \frac{(2m)!(2n)!}{m!n!(m+n)!} \]

Ricordare la definizione del fattoriale di un intero non negativo:

\[ n! = \begin{cases} n\cdot (n-1)! & \text{ se n > 0} \\ 1 & \text{se}\ n=0 \\ \end{cases} \]

Esercizio 6

Se \((a,m)=1\) allora:

\[ a^{k} \equiv a^{k \pmod{\varphi(m)}} \pmod{m} \]

Suggerimento
Utilizzare il teorema di Eulero-Fermat (vedere articolo del blog).

Esercizio 7

Dimostrare che

\[ {n^{n^{n^{n}}} – n^{n^{n}}} \equiv 0 \pmod{9} \]
SOLUZIONE

Se \(3|n\) abbiamo finito. Altrimenti utilizzare il teorema di Eulero-Fermat e l’esercizio 6. Ricordando che \(\varphi(9)=6\), basta dimostrare che \(n^{n^{n}} – n^{n} \equiv 0 \pmod{6}\). Intanto si ha \(
{n^{n^{n}} – n^{n}} \equiv 0 \pmod{2}\). Poiché abbiamo supposto che \(n\) non è divisibile per \(3\), dobbiamo dimostrare che \(
{n^{n^{n}} – n^{n}} \equiv 0 \pmod{3}\). Questa è equivalente alla \(
{n^{n} – n} \equiv 0 \pmod{\varphi(3)}\). Ma \(\varphi(3)=2\) e poiché i due membri della congruenza hanno la stessa parità la formula è dimostrata.

Esercizio 8

Dimostrare che un numero perfetto dispari ha almeno tre fattori primi distinti.

Per i numeri perfetti vedere l’articolo del presente blog, oppure il testo [1].

SOLUZIONE

Distinguiamo i seguenti casi:
1) \(n=p^{k}\)
In questo caso \(\sigma(n)=1+p+ \cdots +p^{k} < 2p^{k}=2n\) contrariamente all’ipotesi che \(n\) è perfetto.
2) \(n=p^{a}q^{b} \)
In questo caso \(\sigma(n)= \sigma(p^{a}) \sigma(p^{b})\). Quindi \(\sigma(n)=p^{a}q^{b}(1 + \frac{1}{p} + \cdots + \frac{1}{p^{a}})(1 + \frac{1}{q} + \cdots + \frac{1}{q^{b}})\). Possiamo maggiorare le due somme con le rispettive serie geometriche ottenendo: \(\sigma(n) < p^{a}q^{b}\frac{1}{1-\frac{1}{p}}\frac{1}{1-\frac{1}{q}}\). Prendendo il caso più sfavorevole per la disuguaglianza \(p=3,q=5\) otteniamo infine \(\sigma(n) <p^{a}q^{b} \frac{1}{1-\frac{1}{3}}\frac{1}{1-\frac{1}{5}}= \frac{15}{8}p^{a}q^{b} < 2n\), contrariamente all’ipotesi che \(n\) è un numero perfetto.

In realtà ad oggi non è stato trovato alcun numero perfetto dispari. Se esistono devono essere numeri molto grandi. Per un riepilogo della situazione della ricerca matematica vedere il seguente link.

Esercizio 9

La congettura di Goldbach afferma che ogni numero pari maggiore di \(2\) è la somma di due numeri primi.
Dimostrare che la congettura di Goldbach è equivalente all’affermazione che ogni numero pari maggiore di \(4\) è somma di \(3\) primi.
Dimostrare anche che la congettura di Goldbach implica che ogni numero dispari maggiore di \(7\) è la somma di tre numeri primi dispari.

La congettura di Goldbach ad oggi non è ancora stata dimostrata. Per un riepilogo dei risultati raggiunti nel tentativo di dimostrare la congettura di Goldbach vedere il seguente link.

Esercizio 10

Ricordiamo la definizione della seguente funzione aritmetica

\[ \pi (x) = |\{p \in \mathbb{P} : p \le x\}| \]

dove \(x\) è un numero reale positivo e \(\mathbb{P}\) rappresenta l’insieme dei numeri primi \(\{2,3,5,7,11, \cdots \}\). Dimostrare le seguenti disuguaglianze:

\[ \begin{split} \frac{\pi (n-1)}{n-1} &< \frac{\pi (n)}{n} \quad \text{ (n primo)} \\ \frac{\pi (n-1)}{n-1} &> \frac{\pi (n)}{n} \quad \text{(n composto)}\\ \end{split} \]
SOLUZIONE

Soluzione
Se \(n\) è un numero composto allora \(\pi(n) = \pi (n-1)\) e quindi la seconda formula è soddisfatta. Se \(n\) è primo, allora \(\pi(n) = \pi (n-1) +1 \). Quindi:

\[ \frac{\pi (n)}{n} – \frac{\pi (n-1)}{n-1} = \frac{1}{n}\left(1 – \frac{\pi (n-1)}{n-1}\right) \]

Da questo deriva subito la prima formula, dato che \(\pi(n) <n\).

La funzione \(\pi (x)\) ha un ruolo importante nello studio della distribuzione dei numeri primi. Un risultato fondamentale è il seguente Teorema dei Numeri Primi:

\[ \lim_{x \to \infty} \frac{\pi (x)}{(\frac {x}{\ln x})}=1 \]

Per una dimostrazione “elementare” del teorema che non utilizza strumenti avanzati dell’analisi matematica vedere [2]. Per una panoramica esaustiva vedere il seguente link.


Bibliografia

[1]Niven, Zuckerman, Montgomery – An introduction to the Theory of Numbers, V edition (Wiley, 1991)

[2]Hardy, Wright – An Introduction to the Theory of Numbers (Oxford U.P.)


0 commenti

Lascia un commento!