Aritmetica
Qualche tempo fa ne misi uno simile...
siano $p$ un primo dispari $h,k$ due soluzioni (intere!!)
della congruenza $p^x\equiv1(x)$. Mostrare che anche
il prodotto $hk$ è soluzione di tale congruenza.
siano $p$ un primo dispari $h,k$ due soluzioni (intere!!)
della congruenza $p^x\equiv1(x)$. Mostrare che anche
il prodotto $hk$ è soluzione di tale congruenza.
Risposte
"ubermensch":
Qualche tempo fa ne misi uno simile...
siano $p$ un primo dispari $h,k$ due soluzioni (intere!!)
della congruenza $p^x\equiv1(x)$. Mostrare che anche
il prodotto $hk$ è soluzione di tale congruenza.
Quindi $p^h -= 1 mod h$ e $p^k -= 1 mod k$, segue $p^(hk) -= 1 mod h$ e $p^(hk) -= 1 mod k$ cioè per alcuni $n,m$
$p^(hk)=nh+1$
$p^(hk)=mk+1$
e $nh=mk$ se $h,k$ sono primi tra loro allora $h|m$ quindi $p^(hk) -= 1 mod hk$.
Ora devo andare... sto pomeriggio provo a rimuovere la condizione di $h,k$ primi fra loro...
Ciao Ciao
eh si Carlo... l'ipotesi che $h,k$ siano coprimi rende il problema
un giochetto da bambini...
un giochetto da bambini...
Ho cercato di risolvere il problema, ma conoscendo più l'algebra astratta che la teoria dei numeri, non riesco a venire a capo della congruenza. Come si risolve?
non lo so!!
una dimostrazione completa non ce l'ho... ho una serie di osservazioni che se ti interessano
posso mettere, ma non prima di lunedi
una dimostrazione completa non ce l'ho... ho una serie di osservazioni che se ti interessano
posso mettere, ma non prima di lunedi
Be' se non sai la soluzione, diventa una situazione ancora più stimolante, farò ancora qualche tentativo per risolvere il problema. Nel frattempo leggerò volentieri le tue osservazioni. Per ora non riesco a sfruttare attivamente l'ipotesi che p sia primo.
Risolto il problema!! La soluzione è anche elegante e breve. La posto entro martedì, oggi non ho tempo di scriverla.
ok... sono curioso di conoscerla!!
Come promesso, ecco la dimostrazione.
Osserviamo che l'enunciato non vale solo per i primi dispari, ma per ogni numero. Dunque l'enunciato è: per ogni numero $a$, se $a^h\equiv 1\mod(h)$ e $a^k\equiv 1\mod(k)$, $a^{hk}\equiv 1\mod (hk)$.\\
Dimostrazione. Abbiamo che $a^{hk}-1=(a^k-1)(1+a^k+a^{k2}+\cdots +a^{k(h-1)})$. Sia ora $d=\mbox{MCD}(h,k)$, e $h=dx$ e $k=dy$: ovviamente $x$ e $y$ sono primi tra loro. Per ipotesi $k|a^k-1$. Inoltre, poiché $d|k$, abbiamo che $d|a^k-1$, dunque $a^k\equiv 1\mod(d)$. Ma allora, $(1+a^k+a^{k2}+\cdots +a^{k(h-1)})\equiv (1+1+1^2+\cdots +1^{h-1})\mod(d)$ e dunque $(1+a^k+a^{k2}+\cdots +a^{k(h-1)})\equiv h\equiv 0\mod(d)$, poiché $d|h$. Dunque $d|(1+a^k+a^{k2}+\cdots +a^{k(h-1)})$. Segue che $kd|a^{hk}-1$ e dunque $d^2y|a^{hk}-1$. Poiché $a^{hk}-1=(a^h-1)(1+a^h+a^{h2}+\cdots +a^{h(k-1)})$, in modo banalmente analogo si dimostra $hd|a^{hk}-1$ e dunque $d^2x|a^{hk}-1$. Ma allora $\mbox{mcm}(d^2x,d^2y)|a^{hk}-1$ (banale proprietà del minimo comune multiplo mcm). Poiché $x$ e $y$ sono primi fra loro, $\mbox{mcm}(d^2x,d^2y)=d^2xy$ e dunque $hk=d^2xy|a^{hk}-1$. Q.E.D.\\\\
Osservo anche che non vale il viceversa: $a^{hk}\equiv 1\mod (hk)$ non implica che necessariamente $a^h\equiv 1\mod(h)$ e $a^k\equiv 1\bmod(k)$. Ecco uno dei tanti controesempi: $3^{4\times5}=1\bmod(4\times5)$, ma $3^{5}=1\mod(5)$ è falso.
Osserviamo che l'enunciato non vale solo per i primi dispari, ma per ogni numero. Dunque l'enunciato è: per ogni numero $a$, se $a^h\equiv 1\mod(h)$ e $a^k\equiv 1\mod(k)$, $a^{hk}\equiv 1\mod (hk)$.\\
Dimostrazione. Abbiamo che $a^{hk}-1=(a^k-1)(1+a^k+a^{k2}+\cdots +a^{k(h-1)})$. Sia ora $d=\mbox{MCD}(h,k)$, e $h=dx$ e $k=dy$: ovviamente $x$ e $y$ sono primi tra loro. Per ipotesi $k|a^k-1$. Inoltre, poiché $d|k$, abbiamo che $d|a^k-1$, dunque $a^k\equiv 1\mod(d)$. Ma allora, $(1+a^k+a^{k2}+\cdots +a^{k(h-1)})\equiv (1+1+1^2+\cdots +1^{h-1})\mod(d)$ e dunque $(1+a^k+a^{k2}+\cdots +a^{k(h-1)})\equiv h\equiv 0\mod(d)$, poiché $d|h$. Dunque $d|(1+a^k+a^{k2}+\cdots +a^{k(h-1)})$. Segue che $kd|a^{hk}-1$ e dunque $d^2y|a^{hk}-1$. Poiché $a^{hk}-1=(a^h-1)(1+a^h+a^{h2}+\cdots +a^{h(k-1)})$, in modo banalmente analogo si dimostra $hd|a^{hk}-1$ e dunque $d^2x|a^{hk}-1$. Ma allora $\mbox{mcm}(d^2x,d^2y)|a^{hk}-1$ (banale proprietà del minimo comune multiplo mcm). Poiché $x$ e $y$ sono primi fra loro, $\mbox{mcm}(d^2x,d^2y)=d^2xy$ e dunque $hk=d^2xy|a^{hk}-1$. Q.E.D.\\\\
Osservo anche che non vale il viceversa: $a^{hk}\equiv 1\mod (hk)$ non implica che necessariamente $a^h\equiv 1\mod(h)$ e $a^k\equiv 1\bmod(k)$. Ecco uno dei tanti controesempi: $3^{4\times5}=1\bmod(4\times5)$, ma $3^{5}=1\mod(5)$ è falso.
ottimo!!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo