\( n \mid 3^n+1 \) se \( n \) dispari

[Gi81]

Trovare tutti gli interi positivi dispari $n$ tali che $n$ divide $3^n +1$.

[dan952]

Risposta flash:

Sia $n$ primo dispari, perché se $n|3^n+1$ allora divide anche $(3+1)^n=4^n$ (si vede sviluppando il binomio di Newton) ma $n$ è un primo diverso da 2 allora questo non può accadere.

[Sk_Anonymous]

Molto intrigante la tecnica.

Non riesco a provare che \(\displaystyle \binom {n} {k} \) per $k=1,2, ..., n-1$ sia un multtiplo di n, se $n$ non è primo.
Anzi se questo fosse vero, sarebbe vero che $n|2^n-2$ e questo non mi risulta in generale.
Direi che può essere utile smanettare un po' con il piccolo teorema di Fermat.

[dan952]

No non vale in generale, ho verificato con n=9.
Cerco un'altra soluzione...

[dan952]

Ricordo brevemente la definizione della funzione di Eulero, sia $n=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, si ha:
$$\psi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots 1-\frac{1}{p_k})$$

Lemma 1. Se $n$ è un intero positivo dispari non primo allora $4| \psi(n)$.

Dim. Supponiamo che $n=p_1 \cdot p_2$, con $p_1$ e $p_2$ primi dispari, si ha $\psi(n)=(p_1-1)(p_2-1)$ poiché $p_1-1$ e $p_2-1$ sono entrambi pari segue $4|\psi(n)$.

Teorema di Eulero. Siano $n$ e $a$ numeri naturali positivi tali che $(n,a)=1$, allora $a^{\psi(n)} -= 1 \mod n$.

Lemma 2 Sia $a$ un intero positivo supponiamo che $b$ è il più piccolo intero positivo tale che $a^{b} -= 1 \mod n$, allora $\forall m>b$ tale che $a^m -= 1 mod n$, segue $b | m$, vale anche il viceversa.

Dim. Se $b$ non divide $m$ allora esistono $k,r$ positivi tali che $m=bk+r$, con $r


Sia $n$ un numero naturale dispari diverso da 1, dal lemma 1 abbiamo che $4 | \psi(n)$, inoltre se $n | 3^n+1$ allora $n$ dividerà anche $3^{2n}-1=(3^n+1)(3^n-1)$, cioè $3^{2n} -= 1 \mod n$, è anche facile verificare che $\psi(n)<2n$, dividiamo due casi:

Caso 1 ( 3 genera $U(ZZ_n)$, cioè $b=\psi(n)$): Dal lemma 2 segue che $\psi(n) | 2n$ ma questo è impossibile poiché $4$ divide $\psi(n)$ ma non divide $2n$.

Caso 2 ($b < \psi(n)$): Segue che $b | 2n$ tuttavia $3^n -= -1 \mod n$ dunque $b$ non divide $n$, se $(n,b)=1$ segue che $b=2$ o $b=1$, in entrambi i casi abbiamo che $9 -= 1 \mod n$ e $3 -= 1 \mod n$, che non sono verificate per alcun $n$ dispari.

[Gi81]

\( b \mid 2n \) e \( b \nmid n \) non implica necessariamente \(b \ \mid 2 \) (controesempio con $n=15$ e $b=10$)

[dan952]

Eh si Giotto hai ragione, errore stupido ma fatale...

Ho dato per scontato che (n,b)=1, cosa non vera in generale.

Non mi resta che ragionare sul prodotto notevole $(3^n+1)=4(3^{n-1}-\cdots +1)$.

[Gi81]

hint:

se $n>1$, sia $p$ il più piccolo primo che divide $n$. Quanto fa $(2n, p-1)$?

[dan952]

A volte mi rendo conto da solo che provo ad uccidere mosche con il fucile a pompa e di fare pure cilecca...

Se $p$ è il più piccolo primo che divide $n$ allora $(n,p-1)=1$ poiché nessun altro primo $q$ che divide $n$ può dividere $p-1$ essendo $q>p$, inoltre $(p-1,p)=1$ banalmente, quindi $(2n,p-1)=2$ se $p>2$. Detto ciò, si ha $3^{2n} -=1\mod p$ dove $p$ è il più piccolo numero primo che divide $n$, sia $d$ il più piccolo intero positivo tale che $3^{d} -=1\mod p$, da Fermat segue che $d|p-1$ e $d|2n$ ma $(2n,p-1)=2$ quindi $d=2$, da cui $3^2 -= 1 \mod p$ che non vale per $p>2$.

[Gi81]

Ottimo!

[Sk_Anonymous]

So bene che ci sono metodi più generali ed eleganti, ma volevo solo la vostra vonferma di non aver commesso vilipendio nei confronti della regina della matematica.

Caso $n=p\cdotq$ con $p$ e $q$ primi.
Se $n|3^n+1$ allora $p|3^n+1$. Ma per il PTF si ha $(3^q)^(p-1) \equiv 1 (mod p)$.
Quindi $3^n+1=(3^q)^(p-1)\cdot3^q+1=(kp+1)3^q+1=kp3^q+3^q+1$ per qualche $k$.
Pertanto, per ipotesi, $p|3^q+1$. Ma per il PTF $3^(q-1) \equiv 1 (mod q)$.
Quindi $3^q+1=3^(q-1)3+1=(hq+1)3+1=3hq+4$. Cioè $q|4$.

PS
non va bene. Ho già trovato un errore, non so se rimediabile.

[dan952]

L'ultima parte quella che dici (senza scriverlo) $q|3^q+1$?

[Sk_Anonymous]

sì, ho confuso p con q.

[Erasmus_First]

"dan95":No non vale in generale, ho verificato con n=9.

Che cos'è che non vale in generale?
Che cos'è che hai vcerifiucato per n = 9?
Guarda che $(4^9 - (3^9 + 1))/9$ fa $26940$.
Io credo che l'unico n dispari divisore di $3^n+1$ sia 1.
________

[dan952]

Mi riferivo ai singoli coefficienti binomiali, infatti $9$ non divide $((9),(3))$.