Un po' di congruenze
Trovare una funzione $f:ZZ^3toZZ$ con le seguenti proprieta':
$f(x,y,z)\equivx(mod3)$, $f(x,y,z)\equivy(mod5)$, $f(x,y,z)\equivz(mod7)$, per tutti gli interi $x,y,z$.
$f(x,y,z)\equivx(mod3)$, $f(x,y,z)\equivy(mod5)$, $f(x,y,z)\equivz(mod7)$, per tutti gli interi $x,y,z$.
Risposte
"Crook":
Trovare una funzione $f:ZZ^3toZZ$ con le seguenti proprieta':
$f(x,y,z)\equivx(mod3)$, $f(x,y,z)\equivy(mod5)$, $f(x,y,z)\equivz(mod7)$, per tutti gli interi $x,y,z$.
$f(x,y,z)=-35x+21y+15z$
Sì, era troppo facile. Proviamo con qualcosa di più interessante.
Sia $p$ un numero primo dispari. Provare che $(1+px)^(p^k)\equiv1+p^(k+1)x(modp^(k+2))$, per ogni intero $x$ e ogni intero non negativo $k$.
Sia $p$ un numero primo dispari. Provare che $(1+px)^(p^k)\equiv1+p^(k+1)x(modp^(k+2))$, per ogni intero $x$ e ogni intero non negativo $k$.
Proviamo a dimostrarlo per induzione:
per k=0 è banalmente verificato, infatti $(1+px)-=1+p(modp^2)$.
Ammettiamo che sia vero per k-1: $(1+px)^(p^(k-1))-=1+p^(k)x(modp^(k+1))$, verifichiamolo per k:
$(1+px)^(p^k)=((1+px)^(p^(k-1)))^p$
per utilizzare il risultato ottenuto con k-1 basta osservare che se $n-=m(modp^(k+1))$ allora $n^p-=m^p(modp^(k+2))$ infatti
$n=m+hp^(k+1)rarrn^p=(m+hp^(k+1))^p=sum_(i=0)^p ((p),(i))m^(p-i)(hp^(k+1))^i-=m^p(modp^(k+2))$
pertanto
$(1+px)^(p^k)=((1+px)^(p^(k-1)))^p-=(1+p^kx)^p(modp^(k+2))-=sum_(i=0)^p ((p),(i))(p^(k)x)^i-=1+p^(k+1)x(modp^(k+2))$
per k=0 è banalmente verificato, infatti $(1+px)-=1+p(modp^2)$.
Ammettiamo che sia vero per k-1: $(1+px)^(p^(k-1))-=1+p^(k)x(modp^(k+1))$, verifichiamolo per k:
$(1+px)^(p^k)=((1+px)^(p^(k-1)))^p$
per utilizzare il risultato ottenuto con k-1 basta osservare che se $n-=m(modp^(k+1))$ allora $n^p-=m^p(modp^(k+2))$ infatti
$n=m+hp^(k+1)rarrn^p=(m+hp^(k+1))^p=sum_(i=0)^p ((p),(i))m^(p-i)(hp^(k+1))^i-=m^p(modp^(k+2))$
pertanto
$(1+px)^(p^k)=((1+px)^(p^(k-1)))^p-=(1+p^kx)^p(modp^(k+2))-=sum_(i=0)^p ((p),(i))(p^(k)x)^i-=1+p^(k+1)x(modp^(k+2))$
Pefetto; l'induzione è la strada più veloce, in questo tipo di problemi.
Ok, ecco un'altra interessante e non difficile.
Sia $m=p^k$, con $p$ primo dispari e $k\ge1$. Dimostrare che $\frac{m-1}2 \equiv \frac{k(p-1)}2(\mod 2)$
Sia $m=p^k$, con $p$ primo dispari e $k\ge1$. Dimostrare che $\frac{m-1}2 \equiv \frac{k(p-1)}2(\mod 2)$
Lo risolvo per...tutti.
Per k=1 la cosa e' evidente.Per k>1 si puo' scrivere:
$(p^k-1)/2-k*(p-1)/2=(p-1)/2*[p^(k-1)+p^(k-2)+...+p+1-k]$
e la differenza in parentesi quadra e' pari indipententemente dalla parita' di k.
karl
Per k=1 la cosa e' evidente.Per k>1 si puo' scrivere:
$(p^k-1)/2-k*(p-1)/2=(p-1)/2*[p^(k-1)+p^(k-2)+...+p+1-k]$
e la differenza in parentesi quadra e' pari indipententemente dalla parita' di k.
karl
Hmm, bella soluzione. Ok, dopo il riscaldamento, un'altra.
Siano $m=\prod_{i=1}^rp_i^{k_i}$ e $n=\prod_{j=1}^sq_j^{l_j}$. Dimostrare che $\frac{m-1}2\frac{n-1}2 \equiv \sum_{i=1}^r\sum_{j=1}^sk_il_j\(p_i-1)/2(q_j-1)/2(\mod2)$
Siano $m=\prod_{i=1}^rp_i^{k_i}$ e $n=\prod_{j=1}^sq_j^{l_j}$. Dimostrare che $\frac{m-1}2\frac{n-1}2 \equiv \sum_{i=1}^r\sum_{j=1}^sk_il_j\(p_i-1)/2(q_j-1)/2(\mod2)$
Ma m,n, e le p,q sono numeri qualunque
o ci sono delle condizioni?
karl
o ci sono delle condizioni?
karl
Dimenticanza mia. Quelle sono le fattorizzazioni canoniche di $m$ e $n$.
Cominciamo con l'osservare che se $a-=a'(mod2)$ e $b-=b'(mod2)$ allora $ab-=a'b'(mod2)$, quindi, data la simmetria della formula, basterà mostrare che $\frac{m-1}2-=\sum_{i=1}^rk_i\(p_i-1)/2(\mod2)$.
Si procede con un'induzione su $r$, per $r=1$ è già stato dimostrato in precedenza, ora dimostriamolo per r+1:
$(p_(r+1)^(k_(r+1))prod_(i=1)^rp_i^(k_i)-1)/2=(p_(r+1)^(k_(r+1))prod_(i=1)^rp_i^(k_i)-1+p_(r+1)^(k_(r+1))-p_(r+1)^(k_(r+1)))/2=$
$=(p_(r+1)^(k_(r+1))(prod_(i=1)^rp_i^(k_i)-1))/2+(p_(r+1)^(k_(r+1))-1)/2-=sum_{i=1}^rk_i\(p_i-1)/2+k_(r+1)(p_(r+1)-1)/2 (mod2)-=sum_{i=1}^(r+1)k_i\(p_i-1)/2 (mod2)$
EDIT: immagino che p=2 fosse da contemplare, o sbaglio?
Si procede con un'induzione su $r$, per $r=1$ è già stato dimostrato in precedenza, ora dimostriamolo per r+1:
$(p_(r+1)^(k_(r+1))prod_(i=1)^rp_i^(k_i)-1)/2=(p_(r+1)^(k_(r+1))prod_(i=1)^rp_i^(k_i)-1+p_(r+1)^(k_(r+1))-p_(r+1)^(k_(r+1)))/2=$
$=(p_(r+1)^(k_(r+1))(prod_(i=1)^rp_i^(k_i)-1))/2+(p_(r+1)^(k_(r+1))-1)/2-=sum_{i=1}^rk_i\(p_i-1)/2+k_(r+1)(p_(r+1)-1)/2 (mod2)-=sum_{i=1}^(r+1)k_i\(p_i-1)/2 (mod2)$
EDIT: immagino che p=2 fosse da contemplare, o sbaglio?
Sono un po' arruginito sulle congruenze e mi chiedevo se
sono possibili anche tra numeri non interi.Come ,per esempio,
avverrebbe se in quella che hai proposto,m ed n (od anche
uno solo di essi) fossero (fosse) pari.
karl
sono possibili anche tra numeri non interi.Come ,per esempio,
avverrebbe se in quella che hai proposto,m ed n (od anche
uno solo di essi) fossero (fosse) pari.
karl
Devo trovare una non dimostrabile per induzione, luca 
.
$m$ ed $n$ devono essere dispari e coprimi; avevo in mente di scriverlo, ma me lo sono dimenticato.
In teoria si potrebbe scrivere una congruenza anche tra numeri razionali, ma essa assume senso quando i termini sono espressi in interi.
. $m$ ed $n$ devono essere dispari e coprimi; avevo in mente di scriverlo, ma me lo sono dimenticato
.In teoria si potrebbe scrivere una congruenza anche tra numeri razionali, ma essa assume senso quando i termini sono espressi in interi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo