Coprimi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
LucaMac
Messaggi: 174
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Coprimi

Messaggio da LucaMac » 22 gen 2016, 23:05

Sembra difficile ma in realtà è facile.
Sembra facile ma in realtà è difficile.
Sembra Teoria dei Numeri ma in realtà è Teoria dei Numeri.
Per ogni $n>1$ sia $$ S_n=\{ x : 1\leq x < n , (x,n)=1\}$$ e sia $$ T_n =\{ x : x,x+1 \in S_n \}$$.
Definiamo due funzioni $\varphi , \psi : \mathbb{Z}^+ \to \mathbb{N}$ tali che $\varphi(n)=|S_n|$ , $ \psi(n)=|T_n|$ per ogni $n \in \mathbb{Z}^+$.
Sia inoltre per ogni $n>1$ definita $f_n: S_n \to \mathbb{N}$ tale che $f_n(k)=\frac{k^{\varphi(n)}-1}{n}$ per ogni $k \in S_n$.
Dimostrare che $$\prod_{t \in T_n} (f_n(t)-f_n(n-t)) \equiv \varphi(n)^{\psi(n)} \pmod{n}$$ per ogni $n>1$.
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

Avatar utente
D.S.R.
Messaggi: 17
Iscritto il: 13 ott 2015, 01:49
Località: MI
Contatta:

Re: Coprimi

Messaggio da D.S.R. » 23 gen 2016, 23:33

Testo nascosto:
Sembra che non prenda il \pmod...
[math]

bern-1-16-4-13
Messaggi: 71
Iscritto il: 23 mag 2015, 18:27

Re: Coprimi

Messaggio da bern-1-16-4-13 » 24 gen 2016, 00:38

Alla fine hai fatto tutti questi giri di parole con funzioni per chiedere di dimostrare un lemma!! :lol:
Testo nascosto:
Lemma:
$$\prod_{t\in T_n}t\equiv 1\pmod{n}\ \ \ \forall n\in\mathbb{N}.$$
Se la sommatoria è vuota allora si presume sia uguale a $1$, quindi per $n\equiv 0\pmod{2}$ la tesi è banalmente vera (quindi da ora in poi nella dimostrazione del lemma i primi nella fattorizzazione di $n$ li supporremo tutti $2$).
La tesi è anche vera per $n$ primo, poiché per Wilson sappiamo che $\left(p-2\right)!\equiv 1\pmod{p}$.
Dimostriamo che la tesi è vera anche per $n=p^k$. Sia $g$ un generatore modulo $p^k$ ( :lol: ).
Allora $$\prod_{i=1}^{p^{k-1}\left(p-1\right)}g\equiv -1\pmod{p^k}.$$Infatti sommando gli esponenti otteniamo $$\prod_{i=1}^{p^{k-1}\left(p-1\right)}g\equiv -1\pmod{p^k}=g^{\frac{p^{k-1}\left(p-1\right)\left(p^{k-1}\left(p-1\right)+1\right)}{2}}=\left(g^{\frac{p^{k-1}\left(p-1\right)}{2}}\right)^{p^{k-1}\left(p-1\right)+1}\equiv \left(-1\right)^{p^{k-1}\left(p-1\right)+1}\equiv -1\pmod{p^k}.$$
Notiamo adesso che per ottenere il resto modulo $p^k$ della produttoria $$\prod_{t\in T_{p^k}}t,$$basta dividere la produttoria $$\prod_{i=1}^{p^{k-1}\left(p-1\right)}g^i$$ per $$\prod_{\substack{1\leq i\leq p^{k-1}\left(p-1\right): \\ g^i\equiv -1\pmod{p}}}g^i.$$Quindi dobbiamo dimostrare che $$\prod_{\substack{1\leq i\leq p^{k-1}\left(p-1\right): \\ g^i\equiv -1\pmod{p^k}}}g^i\equiv -1\pmod{p^k}$$
Sappiamo (per ovvie ragioni che non sto a scrivere) che $g$ deve generare anche modulo $p$, quindi $$\prod_{\substack{1\leq i\leq p^{k-1}\left(p-1\right): \\ g^i\equiv -1\pmod{p}}}g^i=\prod_{i=0}^{p^{k-1}-1}g^{\frac{p-1}{2}+i\left(p-1\right)}.$$
Ora sommando gli esponenti otteniamo che $$\prod_{i=0}^{p^{k-1}-1}g^{\frac{p-1}{2}+i\left(p-1\right)}=\left(g^{\frac{\left(p-1\right)\left(p^{k-1}\right)}{2}}\right)^{p^{k-1}}\equiv \left(-1\right)^{p^{k-1}}\equiv -1\pmod{p^k}.$$
Adesso questo sarà il passo base per impostare un'induzione estesa che dimostri il lemma.
Supponiamo ora che per ipotesi induttiva si abbia $$\prod_{t\in T_a}t\equiv 1\pmod{a},\ \ \ \prod_{t\in T_b}t\equiv 1\pmod{b}\text{con}\ \ \ \ \left(a,b\right)=1,$$ e dimostriamo che $$\prod_{t\in T_{ab}}t\equiv 1\pmod{ab}.$$
Dimostriamo separatamente che si ha che $$\prod_{t\in T_{ab}}t\equiv 1\pmod{a},\ \text{e che}\ \prod_{t\in T_{ab}}t\equiv 1\pmod{b}$$(propongo solo la prima delle due dimostrazioni poiché l'altra è analoga).
Definiamo $m_j\left(x\right)=y:\ \ 1\leq y\leq j,\ \ \ y\equiv x\pmod{j}$.
Allora $$t\in T_{ab}\Longleftrightarrow m_a\left(t\right)\in T_a,\ \ \ m_b\left(t\right)\in T_b.$$
Essendo $a,b$ primi tra loro, come noto $$\forall a_1\leq a,\ b_1\leq b\ \ \ \ \ \ \ \ \ \exists!\ \ s\leq ab:\ \ \ m_a\left(s\right)=a_1,\ \ \ m_b\left(s\right)=b_1.$$




Ma allora questo ci dice che $\forall t\in T_a$ esistono esattamente $\psi\left(b\right)$ elementi di $T_{ab}$ appartenenti alla sua stessa classe di resto modulo $a$ e minori o uguali ad $ab$. In particolare $$\prod_{t\in T_{ab}}t\equiv \left(\prod_{t\in T_{a}}t\right)^{\psi\left(b\right)}\pmod{a}$$e per ipotesi induttiva $$\left(\prod_{t\in T_{a}}t\right)^{\psi\left(b\right)}\equiv 1^{\psi\left(b\right)}\equiv 1\pmod{a}$$che è proprio quello che volevamo dimostrare.





Adesso torniamo al problema. Supponiamo $n\neq 2$ (che si fa a mano). Esplicitando $f_n$ si ha che $$\prod_{t\in T_n}\left(f_n\left(t\right)-f_n\left(n-t\right)\right)=\prod_{t\in T_n}\left(\frac{t^{\varphi\left(n\right)}-\left(n-t\right)^{\varphi\left(n\right)}}{n}\right).$$Sviluppando, semplificando, e tenendo presente che $\varphi\left(n\right)\equiv 0\pmod2$ poiché $n\neq 2$, si ha che $$\prod_{t\in T_n}\left(\frac{t^{\varphi\left(n\right)}-\left(n-t\right)^{\varphi\left(n\right)}}{n}\right)\equiv\prod_{t\in T_n}\left(\frac{\varphi\left(n\right)nt^{\varphi\left(n\right)-1}}{n}\right)\equiv \varphi\left(n\right)^{\psi\left(n\right)}\left(\prod_{t\in T_n}t\right)^{\varphi\left(n\right)-1}\equiv \varphi\left(n\right)^{\psi\left(n\right)}\left(1\right)^{\varphi\left(n\right)-1}\equiv \varphi\left(n\right)^{\psi\left(n\right)}\pmod{n}$$(la penultima congruenza sfrutta il lemma).

La tesi è dimostrata.

Mi scuso per probabilissimi typo!! :oops:

LucaMac
Messaggi: 174
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: Coprimi

Messaggio da LucaMac » 24 gen 2016, 01:12

Ok si (il problema comunque era quello che ho detto io, non il lemma , magari senza $\psi$ e $\varphi$ ma vabbè) .
Comunque esiste una soluzione molto più elementare rispetto a quella con i generatori.
Hint:
Testo nascosto:
se $k \in T_n$ cosa fa $k^{-1}$?
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

bern-1-16-4-13
Messaggi: 71
Iscritto il: 23 mag 2015, 18:27

Re: Coprimi

Messaggio da bern-1-16-4-13 » 24 gen 2016, 01:17

D'accordo, ma quando ho visto che quel passo base veniva (abbastanza facilmente, si tratta solo di fare i calcoli) con i generatori modulo $p^k$ non potevo non usarli!! :lol:

Rispondi