Classe dei resti

[gundamrx91-votailprof]

[tex]a\equiv b_(_m_o_d_ n) \Leftrightarrow a=q_1n+r_1 \land b=q_2n+r_2 \Leftrightarrow r_1 = r_2[/tex]

Cioè due interi [tex]a[/tex] e [tex]b[/tex] sono congrui modulo n se e solo se hanno lo stesso resto nella divisione con n.

Dimostrazione:
[tex]\Rightarrow[/tex]

sia [tex]a = q_1m + r_1[/tex] con [tex]0 \le r_1 < n[/tex] e [tex]b=q_2n+r_2[/tex] implica che [tex]0 \le r_2 < n[/tex]
da cui
[tex]r_1 = a - q_1n[/tex] e [tex]r_2 = b - q_2n[/tex] ; sottraendo membro a membro ottengo

[tex]r_1 - r_2 = (a - q_1n) - (b - q_2n) = a - q_1n - b + q_2n = (a - b) - n(q_1 - q_2)[/tex]

Dalla definizione di [tex]a\equiv b_(_m_o_d_ n) \Leftrightarrow n|a - b[/tex] allora [tex]\exists t \in Z[/tex]
da cui [tex]a - b = nt[/tex] e [tex]nt = a - b[/tex] da cui [tex]nt = a - b = (r_1 - r_2) + n(q_1 - q_2)[/tex]
che implica [tex]r_1 - r_2 = nt - n(q_1 - q_2) = n(t - q_1 + q_2)[/tex] da cui [tex]n|r_1 - r_2[/tex]

Ma da [tex]r_1 \le r_2[/tex] e [tex]0 \le r_1 < n[/tex] e [tex]0 \le r_2 < n[/tex] allora anche [tex]0 \le r_1 - r_2 < n[/tex],
ma da [tex]n|r_1 - r_2[/tex] non può che essere che [tex]r_1 - r_2 = 0[/tex], ovvero [tex]r_1=r_2[/tex]

[tex]\Leftarrow[/tex]

sia [tex]a = q_1n + r[/tex] e [tex]b = q_2n + r[/tex], sottraendo membro a membro ottengo

[tex]a - b = q_1n + r - q_2n - r = q_1n - q_2n = n(q_1 - q_2)[/tex] quindi [tex]n|a - b[/tex]
da cui [tex]a\equiv b_(_m_o_d_ n)[/tex]

Che ne dite, può andare?

Edit: aggiunto modifica come da indicazione.

[Seneca1]

Mi sembra tutto corretto. Per essere precisi dovresti specificare [tex]$r_2 \le r_1$[/tex] per poter scrivere:

"GundamRX91":Ma essendo [tex]0 \le r_1 < n[/tex] e [tex]0 \le r_2 < n[/tex] allora anche [tex]0 \le r_1 - r_2 < n[/tex]

[gundamrx91-votailprof]

Bene, allora correggo e ti ringrazio

[tinex]

Io ne ho una che credo più semplice (per voi), ma io mi sono bloccata.

Dire se è vera la seguente affermazione e giustificare la risposta.
$56^n -= 1$ $ mod 11$, per ogni numero naturale $n$

Il mio ragionamento:

$56^n$ $ = q11 + 1$

$(55+1)^n$ $ = q11 + 1$

$(5x11 +1)^n$ $ = q11 + 1$

Concludo con l'affermare che è FALSA, perché l'ultima equivalenza è vera solo per $n=1$
Ma devo continuare la dimostrazione o può bastare? (sempre che sia corretta)

[Gi81]

"tinex":$56^n -= 1$ $ mod 11$, per ogni numero naturale $n$

Questa affermazione è vera.

"tinex":Il mio ragionamento:

$56^n$ $ = q11 + 1$

$(55+1)^n$ $ = q11 + 1$

$(5x11 +1)^n$ $ = q11 + 1$

Concludo con l'affermare che è FALSA, perché l'ultima equivalenza è vera solo per $n=1$
Ma devo continuare la dimostrazione o può bastare? (sempre che sia corretta)

L'ultima equivalenza non è vera solo per $n=1$, ma per ogni $n$ naturale.
Infatti $56=5*11+1-=1_(mod11)$, quindi $56^n-=1^n-=1$

[tinex]

grazie Gi8!