Classi resto di interi
Ciao a tutti,
dovrei trovare il resto delle divisione per 10 e per 5 di alcuni numeri senza fare la moltiplicazione.
Vi faccio un esempio:
$bar (12345678*90123) = bar12345678 * bar90123 = bar 8 * bar 3 = bar 24 = bar 4 mod 10$
quindi per il mod 10 devo moltiplicare le ultime cifre.
Ma per mod 5 o 3 o 25 come si fa?
Per esempio:
$bar (12345678*90123) = bar 12345678 * bar 90123 = bar 3 * bar 3 = bar 9 = bar 4 mod 5$
però non capisco perche? C'è qualche regola? E come faccio se ho mod 3 e mod 25??
dovrei trovare il resto delle divisione per 10 e per 5 di alcuni numeri senza fare la moltiplicazione.
Vi faccio un esempio:
$bar (12345678*90123) = bar12345678 * bar90123 = bar 8 * bar 3 = bar 24 = bar 4 mod 10$
quindi per il mod 10 devo moltiplicare le ultime cifre.
Ma per mod 5 o 3 o 25 come si fa?
Per esempio:
$bar (12345678*90123) = bar 12345678 * bar 90123 = bar 3 * bar 3 = bar 9 = bar 4 mod 5$
però non capisco perche? C'è qualche regola? E come faccio se ho mod 3 e mod 25??
Risposte
In generale un numero:
- è congruo 2, 5, 10 alla sua cifra delle unità.
- è congruo modulo 3, 9 alla somma delle sue cifre.
Poi i composti te li puoi ricavare facilmente... per esempio il modulo 25 che chiedevi: se il numero scritto in forma decimale è $x = x_nx_(n-1)...x_2x_1$, hai che $x = 100\cdot x_nx_(n-1)...x_3 + x_2x_1$.
Poichè $100\cdot x_nx_(n-1)...x_3 \equiv 0 (mod 25)$ in quanto è multiplo di 100, $x \equiv x_2x_1 (mod 25)$.
Quindi ti trovi che un numero è congruo modulo 25 alle sue ultime due cifre.
Se hai dubbi chiedi pure
- è congruo 2, 5, 10 alla sua cifra delle unità.
- è congruo modulo 3, 9 alla somma delle sue cifre.
Poi i composti te li puoi ricavare facilmente... per esempio il modulo 25 che chiedevi: se il numero scritto in forma decimale è $x = x_nx_(n-1)...x_2x_1$, hai che $x = 100\cdot x_nx_(n-1)...x_3 + x_2x_1$.
Poichè $100\cdot x_nx_(n-1)...x_3 \equiv 0 (mod 25)$ in quanto è multiplo di 100, $x \equiv x_2x_1 (mod 25)$.
Quindi ti trovi che un numero è congruo modulo 25 alle sue ultime due cifre.
Se hai dubbi chiedi pure
che vuol dire alla sua cifra delle unità? puoi spiegarmi prendendo in esame l'esercizio che ho messo di sopra?
Visto che la cifra delle unità di $12345678$ è $8$, $12345678 \equiv 8 (mod 5) \equiv 3 (mod 5)$
Similmente per l'altro.
Similmente per l'altro.
Scusa ma ancora non ho capito 
Perchè
$bar (9085679*120001) = bar 9085679 * bar 120001 = bar 4 * bar 1 = bar 4 mod 5$ ????
Perchè
$bar (9085679*120001) = bar 9085679 * bar 120001 = bar 4 * bar 1 = bar 4 mod 5$ ????
La cifra finale di $9085679$ è $9$ quindi $9085679 \equiv 9 (mod 5) \equiv 4 (mod 5)$
La cifra finale di $120001$ è $1$ quindi $120001 \equiv 1 (mod 5) \equiv 1 (mod 5)$
Da cui segue il prodotto e la tesi... il tuo dubbio qual'è?
La cifra finale di $120001$ è $1$ quindi $120001 \equiv 1 (mod 5) \equiv 1 (mod 5)$
Da cui segue il prodotto e la tesi... il tuo dubbio qual'è?
Ok grazie mille adesso ho capito!
Non è che mi potresti fare un esempio con mod 3??
Per esempio se ho 3548917 come devo fare? e se invece ho mod 4 devo fare lo stesso procedimento del mod5?
Grazie ancora!!!
Non è che mi potresti fare un esempio con mod 3??
Per esempio se ho 3548917 come devo fare? e se invece ho mod 4 devo fare lo stesso procedimento del mod5?
Grazie ancora!!!
Modulo 3 devi fare la somma delle cifre, mentre modulo 4 le ultime due cifre più a destra.
Nel tuo esempio:
$3548917 \equiv 3+5+4+8+9+1+7 (mod 3) \equiv 37 (mod 3) \equiv 3+7 (mod 3) \equiv 1 (mod 3)$
$3548917 \equiv 17 (mod 4) \equiv 1 (mod 4)$
Nel tuo esempio:
$3548917 \equiv 3+5+4+8+9+1+7 (mod 3) \equiv 37 (mod 3) \equiv 3+7 (mod 3) \equiv 1 (mod 3)$
$3548917 \equiv 17 (mod 4) \equiv 1 (mod 4)$
Perchè se ho mod4 devo prendere le ultime due cifre? non le dovevo prendere quando avevo numeri con due cifre tipo 25??
Marix: ogni numero è congruo al numero che consiste delle sue ultime $t$ cifre modulo ogni divisore di $10^t$.
Se ci pensi un attimo risulta ovvio, dato che se $d$ divide $10^t$ allora detto $B$ il numero che consiste delle ultime $t$ cifre di un numero fissato $A$ si ha $A=10^t alpha+B$ per qualche $alpha$ (per esempio $1294810239384 = 12948102393*10^2+84$) e quindi $A equiv 0+B\ mod(d)$.
In particolare un numero è congruo alle sue ultime due cifre modulo ogni divisore di cento ($=10^2$). I divisori di $100$ sono $2,4,5,10,20,25,50$ e quindi ogni numero è congruo alle sue ultime due cifre modulo $2,4,5,10,20,25,50$.
Se ci pensi un attimo risulta ovvio, dato che se $d$ divide $10^t$ allora detto $B$ il numero che consiste delle ultime $t$ cifre di un numero fissato $A$ si ha $A=10^t alpha+B$ per qualche $alpha$ (per esempio $1294810239384 = 12948102393*10^2+84$) e quindi $A equiv 0+B\ mod(d)$.
In particolare un numero è congruo alle sue ultime due cifre modulo ogni divisore di cento ($=10^2$). I divisori di $100$ sono $2,4,5,10,20,25,50$ e quindi ogni numero è congruo alle sue ultime due cifre modulo $2,4,5,10,20,25,50$.
Quindi io in pratica per tutti gli altri numeri all'infuori di 2,4,5,10,20,25,50 (divisori di 100) dovrò usare la somma delle cifre?
"Marix":
Quindi io in pratica per tutti gli altri numeri all'infuori di 2,4,5,10,20,25,50 (divisori di 100) dovrò usare la somma delle cifre?
No.
La somma delle cifre riguarda i divisori di $b-1$, dove $b$ è la base. Siccome noi scriviamo i numeri in base $10$, per noi un numero è congruo alla somma delle sue cifre modulo ogni divisore di $9$. Questa che ho appena detto non è una "regola", è un risultato che si può dimostrare.
quindi dovrò usare la somma solo se ho mod9 o mod3??
Un'altra cosa, se ho per esempio mod11 che non è neanche divisore di 100 come devo fare?
Scusate vi sto assillando abbastanza -.-''
Un'altra cosa, se ho per esempio mod11 che non è neanche divisore di 100 come devo fare?
Scusate vi sto assillando abbastanza -.-''
"Marix":
Un'altra cosa, se ho per esempio mod11 che non è neanche divisore di 100 come devo fare?
Secondo me forse non hai riflettuto abbastanza sulla definizione: due numeri $n$ e $m$ si dicono congrui modulo $d$ se (definizione) $n-m$ è divisibile per $d$. Ne segue che un numero $n$ è congruo modulo $d$ al resto della divisione per $d$.
Quindi per esempio se vuoi conoscere la classe modulo $11$ basta che trovi il resto della divisione per $11$.
Se vuoi conoscere la classe di $2391923$ modulo $11$ fai la divisione con resto di $2391923$ per $11$ e prendi il resto.
Osservo che la divisione con resto devi saperla fare perché la si impara alle elementari.
Tutto il resto sono trucchetti: il fatto che modulo $3$ e modulo $9$ hai la congruenza colla somma delle cifre, il fatto che modulo $10^t$ hai la congruenza colle ultime $t$ cifre e altre cose del genere.
Se vuoi conoscere un "trucchetto" per $11$, puoi usare questo: un numero è divisibile per $11$ se e solo se la somma delle sue cifre di posto dispari è congrua alla somma delle sue cifre di posto pari modulo $11$ (per esempio $239184$ è divisibile per $11$). Quindi per trovare la classe resto non fai altro che togliere unità finché non trovi un multiplo di $11$. Per esempio la classe di $30219293$ modulo $11$ è $5$ dato che $30219293-5=30219288$ è divisibile per $11$.
Ok capito, grazie mille a tutti e due!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo