Aritmetica

[Valerio Capraro]

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.

[carlo23]

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

[Valerio Capraro]

eh si Carlo... l'ipotesi che $h,k$ siano coprimi rende il problema
un giochetto da bambini...

[pjcohen]

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?

[Valerio Capraro]

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

[pjcohen]

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.

[pjcohen]

Risolto il problema!! La soluzione è anche elegante e breve. La posto entro martedì, oggi non ho tempo di scriverla.

[Valerio Capraro]

ok... sono curioso di conoscerla!!

[pjcohen]

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.

[Valerio Capraro]

ottimo!!!!