Teorema di Fermat

[FeddyStra]

Credo di aver trovato una specie di generalizzazione del piccolo teorema di Fermat:
siano a e m due numeri naturali, se m è "squarefree" allora
a^(phi(m)+1)=a (mod m) anche se a e m non sono coprimi.

Qualcuno mi sa dire se è giusta, sbagliata, nuova, esiste già, inutile...?


Ps: mi scuso ma non so ancora usare le formule TeX...
...provvederò al più presto!

[albert_K]

L'ho già vista da qualche parte ma non la conosco bene, magari scrivi una dimostrazione!

Inutile di sicuro non lo è ... (e cosa c'è di inutile in matematica? ), mi pare anche corretta.



P.S. Forse è esagerato mettere come residenza il tuo indirizzo di casa!

[TADW_Elessar]

Intanto la metto in LaTeX così si capisce qualcosa:

siano $ ~a $ e $ ~m $ due numeri naturali.
Se $ ~m $ è squarefree allora

$ \displaystyle a^{\phi(m) + 1} \equiv a \pmod{m} $

anche se $ \mbox{gcd}(a,m) \neq 1 $.

[fph]

P.S. Forse è esagerato mettere come residenza il tuo indirizzo di casa!

Concordo.

[MindFlyer]

Direi che è un'applicazione del teorema cinese del resto.
E' valida per i primi, quindi...

[FeddyStra]

P.S. Forse è esagerato mettere come residenza il tuo indirizzo di casa!

Pensavo che fosse da codardo mascherarmi dietro falso nome, così ho messo in bella vista tutte le mie generalità...
... tuttavia accetto il consiglio e lascerò solo dei dati più generici!


Quanto al teorema... ho pensato un'altra cosa:
eliminando il fatto che m debba essere squarefree, la condizione MCD(a,m)=1 si può sostituire con la condizione che ogni fattore di a compaia al massimo con esponente 1 in m?
Anche questo mi pare che funzioni, ma prima di poter cimentarmi a dimostrarlo credo che dovrò aspettare la fine della scuola...

[MindFlyer]

Certamente, anche questa è un'applicazione del teorema cinese del resto.
Basta dividere la tua tesi in un sistema di congruenze, ognuna modulo una potenza di primo della fattorizzazione di m. Vedi che le congruenze sono soddisfatte in entrmabi i casi (il primo compare o meno nella fattorizzazione di a), e concludi che la stessa contgruenza è vera anche modulo m.

[albert_K]

Credoa sia così...è necessario e sufficiente che ogni fattore primo comune di m e a sia elevato in m ad un esponente che divida l'esponente a cui è elevato in a.

Più esplicitamente,

$ $$a^{\phi(m)+1} \equiv a \pmod{m} $ sse $ $$a= p_1^{e_1}\cdots p_k^{e_k} $ , $ $$m =q_1^{f_1}\cdots q_t^{f_t} $ e $ q_i=p_j \Longrightarrow f_j | e_j $$ , \forall i=1,\dots,t , \forall j=1,\dots,k. $

[albert_K]

No ops... non so perchè mi sia saltata in testa sta cosa. E' sufficiente per i primi comuni, l'esponente in m sia minore o uguale dell'esponente in a.
E non sono sicuro che sia condizione necessaria

Ci ripenso

[dalferro11]

Scusate ma non è semplicemente la generalizzazione scritta in modo diverso data da Eulero sul piccolo teorema di Fermat?

[albert_K]

Non credo, il teorema di Eulero presuppone che a e m siano coprimi.

[dalferro11]

Ho capito...è vero che il teorema di Eulero presuppone che a e m siano coprimi, ma se io divido entrambi i membri per a, non trovo lo stasso teorema?
Il piccolo teorema di Fermat dice:
a^p = a (mod p)

oppure

a^(p-1) = 1 (mod p)

Che è la stessa cosa..........

[pic88]

Ok, allora diremo che il teorema proposto implica il teorema di Fermat, ma non il contrario! Per dimostrare questo non basta Fermat.

[dalferro11]

Mi sermbra che FeddyStra abbia ragione.... però nella dimostrazione molto semplice che utilizza il teorema cinese del resto, bisogna per forza tener presente che $ m $ sia privo di fattori quadratici e che ci sia pure quel $ +1 $ all'esponente altrimenti il teorema risulta falso.
Ovviamente basta dimostrarlo per numeri tali che MCD(a,m)>1.

[albert_K]

$ $$a= p_1^{e_1}\cdots p_k^{e_k} $, $ $$m =q_1^{f_1}\cdots q_t^{f_t} $.

$ $$a^{\phi(m)+1} \equiv a \pmod{m} $
sse $ q_i=p_j \Longrightarrow f_i \leq e_j $.

Mi sembra giusta, si dimostra facilmente con il solito Teorema Cinese.
Però sono sicuro solo al 99% che sia anche una condizione necessaria....qualcuno smentisca o confermi!