Frazione intera

[Mist]

Trovare tutte gli $\displaystyle n\in \mathbb{N}: \frac{2^n-1}{n} \in \mathbb{N}$

[Triarii]

Ci provo
La prima cosa che notiamo è che $ n $ è necessariamente dispari: infatti il numeratore è sempre dispari, quindi il denominatore non può essere pari.
Quindi $ (2;n)=1 $ e $ a^n\equiv 1 (n) $
Sotto queste condizioni vale che $ ord_2 (n)|n $
Supponiamo WLOG che $ n=p $ primo dispari (non può essere 2 per quanto detto sopra)
Dunque $ ord_p (2)|p \Rightarrow \ ord_p (2) = p \lor 1 $
La prima è impossibile perchè l'ordine vale al più $ \phi(p)=p-1 $
La seconda idem perchè se l'ordine fosse 1, $ 2^1\equiv 1 (n) $ che è palesemente falsa per ogni $ n>1 $
Analizziamo ora il caso in cui n sia prodotto di primi dispari.
Grazie al teorema del resto posso condurmi ad un sistema di congruenze modulo le varie potenze dei primi che formano n (tutti i moduli sono fra loro primi).
Ogni LHS del sistema è congrua a 1 modulo i vari $ {p_i}^{\alpha_i} $
Poichè tutti i moduli sono nella forma $ {p_i}^{\alpha_i} $, l'ordine di ciascuna congruenza è $ \phi({p_i}^{\alpha_i})={p_i}^{\alpha_i-1}(p_i-1) $
Quindi l'ordine che cerchiamo è il minimo comune multiplo di tutti i generatori ora trovati. Ma questo è necessariamente pari (infatti ogni ordine ha come fattore $ p-1 $). Ma ciò è assurdo perchè $ ord_n (2) $ (pari ) deve dividere $ n $ (dispari). Anche in questo caso non ci sono soluzioni.
L'unica soluzione è quindi $ n=1 $, l'unico numero che soddisfa la richiesta.
Edit: ho scambiato negli ordini l'indice con il modulo

[Drago96]

Uhm, mi pare sbagliato, perchè (mi pare) che tu stia considerando $2$ come generatore modulo tutti i primi che dividono $n$; ma così non è per molte scelte di $n$, per le quali può essere $\operatorname{ord}_p(2)<p-1$...
Un altro modo per vedere quello che dici tu è che gli $n$ (a parte 1) per cui $\varphi(n)\mid n$ sono tutti e soli quelli della forma $n=2^a\cdot3^b$ con $a\ge1$ (perchè?)

Per questo caso (dove 2 non è generatore) non saprei come procedere, anche perchè non ci ho ancora provato...

[Triarii]

Sì hai ragione, la seconda parte è tutt sbagliata :S
La prima mi sembra giusta però...
Edit. ripensandoci però il 2 essendo primo con ogni modulo $ p^{\alpha} $ dovrebbe essere un generatore o sbaglio? Non è corretto ora?

[Drago96]

Beh, modulo un primo ogni cosa è coprima, ma non per questo tutto è generatore!

[Triarii]

Già che scemo

[Triarii]

Ci riprovo, anche se penso di aver sbagliato di nuovo... (non sto a riscrivere la prima parte perchè quella mi sembrava corretta)
Analizziamo ora il caso in cui n sia prodotto di primi dispari.
Grazie al teorema del resto posso condurmi ad un sistema di congruenze modulo le varie potenze dei primi che formano n (tutti i moduli sono fra loro primi).
Ogni LHS del sistema è congrua a 1 modulo i vari $ {p_i}^{\alpha_i} $.
Ognuno di questi ordini modulo $ {p_i}^{\alpha_i} $ deve dividere $ \phi({p_i}^{\alpha_i})={p_i}^{\alpha_i-1}(p_i-1) $
$ ord_n (2) $ che cerchiamo è il minimo comune multiplo di tutti gli ordini dei vari moduli trovati. Quindi questi devono contenere solo fattori primi contenuti in $ n $ (che sono proprio tutti i $ {p_i}^{\alpha_i} $) Poichè l'ordine di ciascuna congruenze deve essere maggiore di 1 per quanto detto nell'altro post, al minimo il minimo comune multiplo di questi ordini è n : infatti in ogni congruenza del sistema devo andare a scegliermi dei fattori comuni con $ n $, che non possono nemmeno comparire con esponente maggiore di quando compaiono in n (altrimenti $ ord_n (2) $ non dividerebbe $ n $).
Quindi $ ord_n (2)=n $ ma poichè $ ord_n (2)|\phi(n) $ anche $ n|\phi(n) $ che è falso perchè $ \phi(n)>n $ per $ n >1 $

Edit:Sì, direi che è sbagliata...

[Tess]

Mi pare tu stia facendo un giro lungo e largo per niente! Prova ad analizzare per bene il caso di un solo primo!

[Drago96]

Lemma Se $a^n\equiv1\pmod p$ allora $\operatorname{ord}_p(a)\mid\gcd(n,p-1)$
(la dimostrazione è banale, sfrutta due divisibilità note dell'ordine moltiplicativo)

Se $n=1$ allora funziona. Suppongo per assurdo che esista un altro $n$ per cui sia vera la proposizione del testo.
Scrivo allora $n=p^{a_1}p_2^{a_2}\cdots$, ovvero la scomposizione in fattori primi di $n$, con $p<p_i$ per ogni $i$. Ma abbiamo anche detto che $2\nmid n$, quindi $p$ è dispari.
Ora, deve valere $$\displaystyle 2^{p^{a_1}p_2^{a_2}\cdots}\equiv 1\pmod p$$ che per Fermat diventa $$\displaystyle 2^{p_2^{a_2}p_3^{a_3}\cdots}\equiv 1\pmod p$$
Per il lemma $$\operatorname{ord}_p(2)\mid\gcd(p_2^{a_2}p_3^{a_3}\cdots,p-1)$$ma siccome $p$ è più piccolo di tutti i $p_i$, anche i divisori di $p-1$ sono più piccoli dei $p_i$, ed in particolare sono diversi.
Quindi $$\gcd(p_2^{a_2}p_3^{a_3}\cdots,p-1)=1$$ cioè dovrebbe essere $\operatorname{ord}_p(2)=1$, chiaramente assurdo in quanto dovrebbe essere $2\equiv1\pmod p$

[scambret]

Il piccolo teorema di Fermat dice che per ogni a intero e per p primo, $a^p \equiv a \pmod p$ e in forma equivalente se $(a,p)=1$ allora $a^{p-1} \equiv 1 \pmod p$

Simbologia: $(a,p)$ è il massimo comun divisore e se $(a,p)=1$ vuol dire che a e p non hanno fattori in comune.

Inoltre se ti è sconosciuto il simbolo $\equiv$ intendilo cosi: sia $R(x,y)$ il resto del quoziente x diviso per il numero y. Cioè tipo 11:4=2 con resto 3.. Ecco butta il 2, a noi interessa solo il 3 e quindi $R(11,4)=3$ oppure $R(16,5)=1$. Adesso se $R(x,n) = R(y,n)$ allora si dice che $x \equiv y \pmod n$

Quindi $7 \equiv 4 \pmod 3$ perchè $R(7,3)=R(4,3)=1$

[NicolasRossi]

Sisi, semplicemente poiché mi sono completamente sconosciuti concetti come quello di generatore etc. Avevo semplicemente supposto che se $n$ è primo con Fermat si dimostra subito che non esistono soluzioni perché, essendo $n$ dispari, $2$ e $n$ sono necessariamente coprimi. Per $n$ non primo?

[NicolasRossi]

Che ho scritto un'accozzaglia di banalità lo so già