2014

Maggio 2014 - problema 3

Nell'insieme dei numeri naturali positivi, sono detti primi i numeri che hanno esattamente due divisori positivi.

Parte prima.
Si provi che l'insieme dei numeri primi che dividono un qualche intero della forma \(3^n-2\) ha infiniti elementi.

Parte seconda.
Si provi che l'insieme dei numeri primi che dividono un qualche intero della forma \(3^n+4\) ha infiniti elementi.


Livello di difficoltà: Tigrotto da passeggio
Punteggio difficoltà: 40



Tutti i risolutori hanno correttamente provato il primo punto, attraverso la seguente tecnica.
Supponiamo, per assurdo, che l'insieme dei divisori primi dei numeri della forma \(3^n-2\) sia finito, costituito da \(p_1,\ldots,p_k\).
Notiamo preliminarmente che ne' il primo 2 ne' il primo 3 appartengono a questo insieme, in quanto tutti i numeri della forma \(3^n-2\) sono dispari e non multipli di 3.
Prendiamo \(N\) come il prodotto di tutti i \(p_i\) decrementati di uno:
$$N=\prod_{i=1}^k (p_i-1).$$
In virtu' del piccolo Teorema di Fermat, ogni numero della forma \(3^{K(p_i-1)}\) ha resto 1 nella divisione per \(p_i\).
Ne consegue che il numero \(3^N-2\) ha resto \(-1\) nella divisione per \(p_i\), qualunque sia \(p_i\).
Questo pero' e' assurdo, in quanto comporta che \(3^N-2\) non sia diviso da alcuno dei \(p_i\), contro le ipotesi.

Il secondo punto del problema puo' essere affrontato con una tecnica analoga, a meno di venire a capo di una piccola complicazione tecnica.
Come prima, supponiamo che l'insieme dei divisori primi dei numeri della forma \(3^n+4\) sia finito, costituito da \(p_1,\ldots,p_k\).
Come prima, ne' 2 ne' 3 appartengono a tale insieme, e preso \(N\) come il prodotto dei \(p_i\) decrementati di uno, si ha:
$$ 3^N + 4 \equiv 5\pmod{p_i} $$
qualunque sia \(p_i\). Per concludere come nel punto precedente, bisogna allora escludere l'eventualita' che \(3^N+4\) sia una potenza di cinque.
Qui si presentano molte opzioni.

Una possibilita' e' quella di constatare che \(N\) e' necessariamente un multiplo di 20, in quanto \(3^3+4=31\)
e \(3+4=7\) comportano l'appartenenza di 7 e 31 all'insieme dei \(p_i\), dunque il fatto che \(N\) sia un multiplo di \((7-1)\cdot(31-1)=180\).
Il Teorema di Eulero (generalizzazione del piccolo Teorema di Fermat) comunica allora che vale:
$$ 3^N + 4 \equiv 5 \pmod{25}, $$
per cui, se \(3^N+4\) e' una potenza di cinque, e' esattamente cinque. Tuttavia \(3^N+4\) e' ben piu' grande di 5.

Un'altra strada (seguita da Drago e Lasker) e' quella di osservare che l'identita'
$$ 3^N + 4 = 5^k $$
puo' essere realizzata solo se sia \(N\) che \(k\) sono pari (e' sufficiente considerare l'identita' modulo 3 e modulo 5).
In tal caso, \(N=2A\) e \(k=2B\) comportano che si abbia:
$$ 4 = (5^B+3^A)(5^B-3^A), $$
dunque o entrambi i fattori sulla destra sono, in valore assoluto, pari a \(2\), o il piu' grande e' pari a 4 e il piu' piccolo a 1. La disamina dei casi è molto rapida.

Gottinger, invece, modifica la costruzione del punto precedente, prendendo
$$M=\prod_{i=1}^{k}p_i(p_i-1).$$
In tal modo ha garantita la piu' forte condizione:
$$ \forall p_i,\qquad 3^M + 4 \equiv 5\pmod{p_i^2},$$
che gli permette di concludere immediatamente, come nella prima possibilita' presentata.
Sottolineiamo che questo tipo di approccio e' facilmente passibile di generalizzazione - rimandiamo al forum per ulteriori discussioni.