Dimostrazione equivalenza enunciati aritmetica modulare
Leggendo questo articolo di wikipedia mi è sorto in mente questo quesito:
QUESITO
Siano \(\displaystyle a,b,n,k \in \mathbb{N} \) e \(\displaystyle a>0 , \; b>0 , \; n>0 , \; k>0 \). Inoltre \(\displaystyle a-b=k \, n \). Indicato con % l'operazione di resto della divisione tra numeri interi, dimostrare che \(\displaystyle a\%n = b\%n \).
PROPOSTA MIA
Vi sembra corretta? Disponete di una dimostrazione più elegante?
QUESITO
Siano \(\displaystyle a,b,n,k \in \mathbb{N} \) e \(\displaystyle a>0 , \; b>0 , \; n>0 , \; k>0 \). Inoltre \(\displaystyle a-b=k \, n \). Indicato con % l'operazione di resto della divisione tra numeri interi, dimostrare che \(\displaystyle a\%n = b\%n \).
PROPOSTA MIA
Vi sembra corretta? Disponete di una dimostrazione più elegante?
Risposte
Nella tua dimostrazione non va bene il fatto che usi l'identità tra polinomi perché lavori sui naturali e non su polinomi.
Ti faccio un controesempio considera $x=a+b$ , y = $b+a$ puoi dire che $x=y=> a=b , b=a$? non credo.
infatti considera il caso numerico
$x=2+1$ , $y=1+2$
per il P.I.P
si avrebbe che
$2=1 , 1=2$ assurdo!.
-----------------------------------------------------------------------------------------------------------------
La tua proposizione non dice nient'altro che :
Siano $n,k,a,b in NN , a,b,k,a,b$ strettamente positivi.
$AA a,b in NN $ si fissa una relazione $R$ del tipo : $aRb <=> a-b=nk <=> n|a-b$
Allora $a,b$ hanno lo stesso resto se divisi per $n$.
Ci provo.
dim
Per ipotesi, supponiamo che $a>b$ e che $n,k >0$. e che inoltre $a-b = nk >0 $
Consideriamo la divisione euclidea di $a$ per $n$ e $b$ per $n$. E supponiamo per assurdo che $r_1!=r_2 $ e in particolare che $r_1-r_2!=0$.
Abbiamo che
$a=nq_1+r_1$ con $0<=r_1
Ora, $n|a-b$ , ed $n|n(q_1-q_2)$ pertanto $n| r_1-r_2$ il che è un assurdo, visto che $r_1-r_2
Spero di non aver detto cavolate
ciao!
Ti faccio un controesempio considera $x=a+b$ , y = $b+a$ puoi dire che $x=y=> a=b , b=a$? non credo.
infatti considera il caso numerico
$x=2+1$ , $y=1+2$
per il P.I.P
si avrebbe che
$2=1 , 1=2$ assurdo!.
-----------------------------------------------------------------------------------------------------------------
La tua proposizione non dice nient'altro che :
Siano $n,k,a,b in NN , a,b,k,a,b$ strettamente positivi.
$AA a,b in NN $ si fissa una relazione $R$ del tipo : $aRb <=> a-b=nk <=> n|a-b$
Allora $a,b$ hanno lo stesso resto se divisi per $n$.
Ci provo.
dim
Per ipotesi, supponiamo che $a>b$ e che $n,k >0$. e che inoltre $a-b = nk >0 $
Consideriamo la divisione euclidea di $a$ per $n$ e $b$ per $n$. E supponiamo per assurdo che $r_1!=r_2 $ e in particolare che $r_1-r_2!=0$.
Abbiamo che
$a=nq_1+r_1$ con $0<=r_1
Ora, $n|a-b$ , ed $n|n(q_1-q_2)$ pertanto $n| r_1-r_2$ il che è un assurdo, visto che $r_1-r_2
Spero di non aver detto cavolate
ciao!
non ho controllato la tua dimostrazione, lo farò appena possibile
Due domande:
1) cosa intendi con \( a|b \)
2) i polinomi non possono avere coefficenti naturali? Quello mio è un polinomio in \( n \), nel tuo controesempio (anche quello numerico) non ci sono polinomi
Due domande:
1) cosa intendi con \( a|b \)
2) i polinomi non possono avere coefficenti naturali? Quello mio è un polinomio in \( n \), nel tuo controesempio (anche quello numerico) non ci sono polinomi
1) In $NN$ vale che $a|b <=> EE q in NN : b=aq$
2) No. Un polinomio ha coefficienti in un $A$ (anello). Ed $NN$ non lo e' . E inoltre un polinomio spesso è visto come una scrittura formale del tipo
$f(X) = \sum_(i=0)^na_ix^i$. Ma in realtà è una successione definitivamente nulla in $A$ (anche se poi le due cose risultano essere equivalenti)
Il tuo $n$ non è un polinomio, è un numero naturale.
2) No. Un polinomio ha coefficienti in un $A$ (anello). Ed $NN$ non lo e' . E inoltre un polinomio spesso è visto come una scrittura formale del tipo
$f(X) = \sum_(i=0)^na_ix^i$. Ma in realtà è una successione definitivamente nulla in $A$ (anche se poi le due cose risultano essere equivalenti)
Il tuo $n$ non è un polinomio, è un numero naturale.
E' anche un se e solo se.
Comunque volendo con le congruenze ti ricavi:
[tex]a-b=kn \Longrightarrow a-b \equiv kn \pmod n[/tex]
Da cui [tex]a-b \equiv 0 \pmod n[/tex]. E quindi: [tex]a\equiv b \pmod n[/tex].
Comunque parrebbe che la tua dimostrazione (quella iniziale) vada bene, ma l'ultima parte spiegala in modo diverso.
Cio sia [tex]\beta[/tex] sia [tex]\alpha[/tex] sono minori stretti di $n$. Quindi affinchè la loro differenza sia divisibile per $n$ è necessario che siano uguali. Se fossero diversi la loro differenza in modulo sarebbe compresa tra $1$ ed $n-1$ che non è divisibile per $n$.
Comunque volendo con le congruenze ti ricavi:
[tex]a-b=kn \Longrightarrow a-b \equiv kn \pmod n[/tex]
Da cui [tex]a-b \equiv 0 \pmod n[/tex]. E quindi: [tex]a\equiv b \pmod n[/tex].
Comunque parrebbe che la tua dimostrazione (quella iniziale) vada bene, ma l'ultima parte spiegala in modo diverso.
Cio sia [tex]\beta[/tex] sia [tex]\alpha[/tex] sono minori stretti di $n$. Quindi affinchè la loro differenza sia divisibile per $n$ è necessario che siano uguali. Se fossero diversi la loro differenza in modulo sarebbe compresa tra $1$ ed $n-1$ che non è divisibile per $n$.
"xXStephXx":
E' anche un se e solo se.
Comunque volendo con le congruenze ti ricavi:
[tex]a-b=kn \Longrightarrow a-b \equiv kn \pmod n[/tex]
Da cui [tex]a-b \equiv 0 \pmod n[/tex]. E quindi: [tex]a\equiv b \pmod n[/tex].
xXStephXx, hai ragione. Ma allora dovresti definire opportunamente $-=_n$.
Dire che $a-b=kn <=> n|a-b <=> a-=b(modn) <=>[a]_n=_n$ per definizione di congruenza, questo va bene. Ma cosa ti permette di dire che $a,b$ hanno lo stesso resto se divisi per $n$?. Va dimostrato
Alla fine hai solo riscritto l'ipotesi iniziale $a-b=kn$ in un'altro modo.
Alla fine la dimostrazione di raffamaiden va bene,ma è completamente sbagliata quando introduce il principio di identità dei polinomi. Ciò la rende sbagliata.
ciò che si può dire è quanto segue :
Lui considera la divisione di $a$ per $n$ e $b$ per $n$ e ottiene una cosa del tipo
$a=nq_1+r_1$ $0<=r_1
allora
$b-a=n(q_2-q_1)+(r_2-r_2)$
per ipotesi $n|b-a$
inoltre $n|n(q_1)$ e $n|n(q_2) $ quindi $n|n(q_2-q_1)$
ma allora $n|b-a ^^ n|n(q_2-q_1) => n|(r_2-r_1)
Quella che ho scritto là non voleva essere proprio una dimostrazione, era giusto per dire che con quelle nozioni veniva da sè. La dimostrazione che volevo mettere era quella iniziale più la conclusione finale fatta in quell'altro modo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo