Ogni n > 2 tale che 1/2 * phi(n) = 1 mod 6

[HiTLeuLeR]

Questo invece proviene dalle olimpiadi indiane del 2005. Facile!

Determinare ogni intero n > 2 tale che $ \displaystyle\frac{1}{2}\varphi(n) \equiv 1 \bmod 6 $.

[Boll]

Determinare ogni intero n > 2 tale che $ \displaystyle\frac{1}{2}\varphi(n) \equiv 1 \bmod 6 $.

Il compilatore del sito fa le bizze, la spiego senza LaTeX.

Se abbiamo più di un primo dispari, avremo che la phi/2 è pari, assurdo, se n è multiplo di 4, la phi/2 è pari, assurdo. Se n è "2*dispari", la phi è identica a quella di "dispari".

n=p^k
phi=p^k-p^(k-1) è necessario e sufficente che sia 2 mod 6 ma non multiplo di 4.

se p è 3, avremo un multiplo di tre nella phi/2, analizzando la tabella 3*k mod 6 con k variabile, se ne deduce l'impossibilità.

se p è 1 mod 6, allora phi è zero mod 6, assurdo
se p è -1 mod 6 abbiamo i casi
i) k pari, 1-(-1)=2
ii) k dispari, -1-(1)=-2

prendiamo quindi il primo caso
n=p^(2j)
phi=p^(2j)-p^(2j-1)
facciamo i casi modulo 4
i) p==1, 1-1=0 assurdo
ii) p==-1, 1+1=2, che verifica

Quindi sono soluzioni tutti i numeri della forma n=p^(2j) e n=2*p^(2j), dove j è un intero positivo è p un primo congruo a -1 modulo 12 (ne esistono infiniti per Dirilecht)

[HiTLeuLeR]

[...] se n è multiplo di 4, la phi/2 è pari, assurdo.

...ma questo non è vero: $ \displaystyle\frac{1}{2}\varphi(4) = 1 $.

[Boll]

I casi particolari uccidono le dimostrazioni... Per ogni multiplo di 4 >4 funziona, aggiungiamo quindi 4 alle soluzioni.

[Pigkappa]

Scusate ma cosa è phi? Io ero rimasto alla sezione aurea ma qua non credo c'entri niente

[Boll]

Se $ n\in \mathbb{N} $ allora $ \phi(n)=|A| $ dove $ A:=\{k\in \mathbb{N}| (k,n)=1 \land k\le n\} $

Questa è la definizione da sborone (spero corretta, magari ho dimenticato qualche simbolo ). In pratica la $ \phi(\cdot) $ è una funzione aritmetica, che associa ad ogni naturale il numero dei numeri coprimi ad esso e minori o uguali allo stesso.

[HiTLeuLeR]

se p è 3, avremo un multiplo di tre nella phi/2, analizzando la tabella 3*k mod 6 con k variabile, se ne deduce l'impossibilità.

Al di là del giro di parole: $ \displaystyle\frac{1}{2}\varphi(3) = 1 $, quindi $ n = 3 $ ed $ n = 6 $ stanno ovviamente *dentro* al set delle soluzioni possibili. Soltanto non mi è chiaro se tu ce li hai inclusi, oppure no... Il resto va bene!

[Gauss_87]

Quindi sono soluzioni tutti i numeri della forma n=p^(2j) e n=2*p^(2j), dove j è un intero positivo è p un primo congruo a -1 modulo 12 (ne esistono infiniti per Dirilecht)

Da dove ricavi che p è un primo congruo a -1 modulo 12???

Cmq, io ho provato a risolvere il problema così:

Ovviamente $ \phi(n) $ deve essere del tipo $ 2*Dispari $

Sia $ n $ Pari:
$ n = 2^ap^bq^c... $ con $ p,q,... $ Dispari.
$ \phi(n)=2^{a-1}p{b-1}...(p-1)(q-1)... $, dove
$ 2^{a-1},(p-1),(q-1),... $ sono Pari:
solo uno di essi deve essere $ 2 $ o $ 2*Dispari $,
$ n $ non può avere più di un divisore dispari.
1) $ 2^{a-1}=2 \Leftrightarrow a=2 \Leftrightarrow n = 4 $
2) $ 2^{a-1}=1 \Leftrightarrow a=1 \Rightarrow n=2 \cdot p^b $.

Sia $ n $ Dispari:
Anche in questo caso $ n $ non può avere più di un divisore dispari.
$ n=p^b $,
quindi basta trovare le soluzioni per $ n=p^b $ perchè:
$ \phi(2p)=\phi(p) $, cioè è moltiplicativa.

$ \phi(n)=p^b - p^{b-1} \equiv 1 \bmod 6 $

Quindi $ p $ è: $ 3 $ oppure: $ p \equiv \pm 1 \bmod 6 $:
1) $ n=3^b \Rightarrow \frac{\phi(n)}{2}=3^{b-1} \equiv 1 \cmod 6 \Rightleft arrow b=1 \Rightarrow n = 3, n = 6 $

2) $ p \equiv 1 \bmod 6 \Rightarrow p^b - p^{b-1} \equiv 0 \bmod 6 $, assurdo sia per $ b $ Pari che Dispari.
$ p \equiv -1 \bmod 6 \Rightarrow p^b - p^{b-1} \equiv 2 \bmod 6 \Rightleftarrow b $ è Pari:
$ n=p^{2k}, n=2 \cdot p^{2k} $
$ \forall k \in Z^+ $ e $ p \equiv -1 \bmod 6 $ primo.

Lo so le soluzioni in mod 6 non sono corrette, ma la mia domanda è:
da dove salta fuori il mod 12 ???