Esiste sempre un $k$

[Delfad0r]

Dati $n,m$ interi positivi coprimi, dimostrare che esiste sempre un $k$ intero positivo tale che
$$
n\mid m^k+k
$$

[luca95]

Se n è primo è facile...

Testo nascosto:

Le condizioni equivalgono a $ m^k \equiv -k \pmod{n} $
e per il piccolo teorema di fermat $ m^{n-1}\equiv 1 \pmod{n} $
cioè $ m^{n-1}\equiv -n+1 \pmod{n} $
quindi $ n-1 $ è il $ k $ cercato

[matpro98]

Ovviamente è giusto, ma il bello dell'esercizio è quando n non è primo

[erFuricksen]

Ci provo eh

Considero un certo $ k = \alpha \phi (n) + a $
allora è necessario che $ n \mid m^{\alpha \phi (n) + a} + \alpha \phi (n) + a $
ma siccome $ m^{\alpha \phi (n) + a} \equiv m^a [n] $
allora equivale a scrivere $ n \mid m^a + \alpha \phi (n) + a $
quindi $ m^a + \alpha \phi (n) + a = \beta n $
$ \beta n - \alpha \phi (n) = m^a + a $
Ma per il teorema di Bezout sappiamo che LHS può assumere ogni valore dell'insieme $ \gcd (n,\phi (n)) \cdot \mathbb{N} $
Pertanto possiamo affermare che è vero se esiste un $ a $ tale che $ \gcd (n,\phi (n)) \mid m^a + a $
Siccome $ (n,m)=1 $ allora anche $ (\gcd (n, \phi (n)),m)=1 $
Inoltre dato che $ \phi (n) < n $ allora $ \gcd (n,\phi (n))<n $
Quindi avendo $ \gcd (n,\phi (n)) \mid m^a + a $ ci ritroviamo in una situazione identica a quella di partenza (essendo m e gcd coprimi) e con un numero inferiore ad n che divide il tutto; pertanto possiamo ripetere lo stesso procedimento (e ovviamente il valore che divide diminuirà continuamente) fino a quando non otterremo $ 1 \mid m^x + x $ che è sempre vero

[Delfad0r]

Propongo la seguente generalizzazione.
Dati $n,m$ interi positivi, dimostrare che esiste sempre un $k$ intero positivo tale che
$$
n\mid m^k+k
$$

[erFuricksen]

Beh in questo caso la dimostrazione che ho fornito è sempre valida, bisogna solamente apportare l'accorgimento seguente
$ k= \gcd (m,n) \cdot (\alpha \phi (n) + a) $ riconducendo il caso ad un caso in cui $ (m,n)=1 $

Sempre che quella prima sia corretta

[Delfad0r]

Quella prima è corretta, ma non mi è chiarissimo come fai a ricondurti sempre al caso $(n,m)=1$; se potessi essere un poco più esplicito...

[erFuricksen]

Mmmm.. Avevo dimenticato che k è anche all'esponente e varia la congruenza di m sorry, come non detto, lascia perdere