[Ammissione WC16] TdN 2: $n$ non primo divide $3^{n-1}-2^{n-1}$

[Talete]

NON pubblicate la soluzione prima delle 23:59 di oggi!

Dimostrare che esistono infiniti interi positivi composti $n$ tali che $n$ divida $3^{n-1}-2^{n-1}$.

[Giovanni_98]

Testo nascosto:

Prendiamo $n=3^{2^k}-2^{2^k}$ con $k$ intero $\ge 2$. Notiamo che $$n=\prod_{i=0}^{k-1}( 3^{2^i} + 2^{2^i} )$$poichè $k \ge 2$ i termini della produttoria maggiori di $1$ sono almeno $2$ e quindi $n$ è composto.

Lemma : $v_2(3^{3^{2^k}-2^{2^k}-1}-2^{3^{2^k}-2^{2^k}-1}-1)=k+2$ per qualsiasi $k \ge 2 $ intero.
Dimostrazione : Dal momento che $2^{k+2} \leq 2^{2^k}$ (si dimostra banalmente per induzione) è sufficiente dimostrare che $2^{k+2} \mid \mid 3^{2^k}-1$. Riscrivo come $2^{k+2} \mid\mid 9^{2^{k-1}}-1$. Dal momento che $4 \mid 9-1$ posso applicare LTE e quindi $v_2(9^{2^{k-1}}-1) = v_2(8) + v_2(2^{k-1}) = k+2$.

Scriviamo $n=2^{k+2} \cdot q$ con $(q,2)=1$ per il lemma precedente. Allora deve valere $$3^{2^k}-2^{2^k} \mid 3^{2^{k+2}\cdot q} - 2^{2^{k+2}\cdot q}$$Dal momento che $q$ è dispari si ha che $3^{2^{k+2}}-2^{2^{k+2}} \mid 3^{2^{k+2}\cdot q} - 2^{2^{k+2}\cdot q}$ ma $$3^{2^{k+2}}-2^{2^{k+2}}=(3^{2^{k+1}}-2^{2^{k+1}})(3^{2^{k+1}}+2^{2^{k+1}})=(3^{2^{k}}-2^{2^{k}})(3^{2^{k}}+2^{2^{k}})(3^{2^{k+1}}+2^{2^{k+1}})$$e quindi la tesi è dimostrata.

[Troleito br00tal]

Per i più coraggiosi: provate a risolverlo con le proprietà dei polinomi ciclotomici!

Hanno anche aperto apposta un bel thread

viewtopic.php?f=26&t=19719

[Saro00]

Sapevo che poteva venire con quei famigerati polinomi, ora che l'hai detto proveró.
Metto in spoiler 3 idee per risolverlo

Testo nascosto:

$ n=3^{2^n}-2^{2^n} \forall n \in \mathbb{N} n\ge 2 $

Testo nascosto:

$ n=3^{3^n}-2^{3^n} \forall n \in \mathbb{N} n\ge 2 $

Testo nascosto:

$ n=3^{p}-2^{p} \forall n \in \mathbb{P} $ e per garantire la primalitá di $ n $ lo mettiamo congruo a 2 o 4 modulo 5 (serve peró Dirichlet)