problemino facile (dal test per l'ammissione alla scuola superiore di Udine 2005)
trovare (e dimostrare) i criteri di divisibilità per 3, 11 e 13 di un numero naturale $ $n$ $ scritto in base 12
criteri divisibilità base 12
$ n=A+12B+12^2C+12^3C+.... $
Il numero è divisibile per $ 3 $ se e solo se l'ultima cifra è divisibile per $ 3 $. Infatti se $ A $ è divisibile per $ 3 $ siamo a posto, mentre se non lo è non ci siamo (3 divide comunque tutti gli altri addendi della scrittura polinomiale).
Un numero in base 12 è congruo alla somma delle sue cifre modulo 11. Dunque $ n $ è divisibile per 11 se e solo se, detta $ S $ la somma delle sue cifre (in base 10 ovviamente) si ha $ S\equiv 0 \ (mod \ 11) $.
Adesso penso al 13...
Il numero è divisibile per $ 3 $ se e solo se l'ultima cifra è divisibile per $ 3 $. Infatti se $ A $ è divisibile per $ 3 $ siamo a posto, mentre se non lo è non ci siamo (3 divide comunque tutti gli altri addendi della scrittura polinomiale).
Un numero in base 12 è congruo alla somma delle sue cifre modulo 11. Dunque $ n $ è divisibile per 11 se e solo se, detta $ S $ la somma delle sue cifre (in base 10 ovviamente) si ha $ S\equiv 0 \ (mod \ 11) $.
Adesso penso al 13...
"Il fatto che un'opinione sia ampiamente condivisa, non è affatto una prova che non sia completamente assurda" B. Russell
Detta $ S_p $ la somma delle cifre di posto pari e $ S_d $ la somma delle cifre di posto dispari, si ha $ n\equiv S_p+12S_d \equiv S_p+13S_d-S_d \equiv S_p-S_d \ (mod \ 13) $. Dunque deve essere che il modulo della differenza tra la somma delle cifre di posto pari e la somma delle cifre di posto dispari è divisibile per 13.
Puoi confermare o smentire?
Sono le prime volte che lavoro con i criteri di divisibilità e sono ancora un po' insicuro..
Puoi confermare o smentire?
Sono le prime volte che lavoro con i criteri di divisibilità e sono ancora un po' insicuro..
"Il fatto che un'opinione sia ampiamente condivisa, non è affatto una prova che non sia completamente assurda" B. Russell
Russel mi ha preceduto sul tempo...confermo i suoi risultati...
A parte alcune affermazioni non motivate (gente con un pò di occhio ci arriva, però sempre meglio essere esaurienti!), c'è solo una piccola imperfezione: qui dici
Basta semplicemente dire che la somma delle cifre deve essere congrua a zero modulo 11, visto che la relazione "essere congruo a" è indipendente dalla base che scegli...scusami per la pignoleria!
Ciao
A parte alcune affermazioni non motivate (gente con un pò di occhio ci arriva, però sempre meglio essere esaurienti!), c'è solo una piccola imperfezione: qui dici
La somma non deve essere per forza in base 10...siamo solo noi che siamo capaci di fare conti e congruenze con quella base...Russell ha scritto:Un numero in base 12 è congruo alla somma delle sue cifre modulo 11. Dunque $ $n $ è divisibile per 11 se e solo se, detta $ $S $ la somma delle sue cifre (in base 10 ovviamente) si ha $ $S\equiv 0 \ (mod \ 11) $.
Basta semplicemente dire che la somma delle cifre deve essere congrua a zero modulo 11, visto che la relazione "essere congruo a" è indipendente dalla base che scegli...scusami per la pignoleria!
Ciao
Scusarti?? Anzi!! Grazie di averlo precisato...è un'informazione in più!
Dopo ci rifletto sopra!
Quanto a saltare passaggi...è vero...ero un po' di fretta e ho saltato di trascrivere qualche dimostrazionacina veloce che ho fatto su carta.
Magari appena ho tempo completo...
Dopo ci rifletto sopra!
Quanto a saltare passaggi...è vero...ero un po' di fretta e ho saltato di trascrivere qualche dimostrazionacina veloce che ho fatto su carta.
Magari appena ho tempo completo...
"Il fatto che un'opinione sia ampiamente condivisa, non è affatto una prova che non sia completamente assurda" B. Russell
Rimedio alle incompletezze...
Scriviamo $ n $ in forma polinomiale: $ n=A+12B+12^2C+12^3D+12^4E+... $
DIVISIBILITA' PER 3
$ n $ è divisibile per $ 3 $ se e solo se la sua ultima cifra è divisibile per $ 3 $.
Se $ A $ è divisibile per $ 3 $ allora anche $ n $ lo è. In caso contrario $ 3 $ divide tutti e soli i fattori diversi da $ A $, e ciò implica che $ n $ non è divisibile per $ 3 $.
DIVISIBILITA' PER 11
$ n $ è divisibile per $ 11 $ se e solo se la somma delle sue cifre è divisibile per $ 11 $.
Dimostriamo intanto per induzione che $ 12^k\equiv 1 \ (mod \ 11) $ ($ k>0 $). Per $ k=1 $ abbiamo $ 12\equiv 1 \ (mod \ 11) $, vero perchè $ 12-1=11=1\cdot 11 $. Supponiamo la tesi vera per $ k=h $, ovvero $ 12^h\equiv 1 \ (mod \ 11) $, moltiplichiamo per $ 12 $ entrambi i membri della congruenza ottenendo $ 12^{h+1}\equiv 12\equiv 1 \ (mod \ 11) $.
Abbiamo conseguentemente:
$ A\equiv A \ (mod \ 11), 12B\equiv B \ (mod \ 11), 12^2C\equiv C \ (mod \ 11), $ etc. Sommando tutte le congruenze otteniamo $ n\equiv S \ (mod \ 11) $, dove $ S $ è la somma delle cifre di $ n $. Ne viene la tesi.
DIVISIBILITA' PER 13
$ n $ è divisibile per $ 13 $ se e solo se il valore assoluto della differenza tra la somma delle cifre di posto pari e la somma delle cifre di posto dispari è divisibile per $ 13 $.
Dimostriamo intanto per induzione che $ 12^{2k}\equiv 1 \ (mod \ 13) $ ($ k>0 $). Per $ k=1 $ abbiamo $ 144\equiv 1 \ (mod \ 13) $, vero perchè $ 144-1=11\cdot 13 $. Supponiamo la tesi vera per $ k=h $, ovvero $ 12^{2h}\equiv 1 \ (mod \ 13) $, moltiplichiamo per $ 12^2 $ entrambi i membri della congruenza ottenendo $ 12^{2(h+1)}\equiv 12^2\equiv 1 \ (mod \ 13) $.
Ora ci serve dimostrare che $ 12^{2k+1}\equiv 12 \ (mod \ 13) $ ($ k>0 $). Per $ k=1 $ abbiamo $ 12^3\equiv 12 \ (mod \ 13) $, vero perchè $ 1728-12=132\cdot 13 $. Supponiamo la tesi vera per $ k=h $, ovvero $ 12^{2h+1}\equiv 12 \ (mod \ 13) $, moltiplichiamo per $ 12^2 $ entrambi i membri della congruenza ottenendo $ 12^{2(h+1)+1}\equiv 12^3\equiv 12 \ (mod \ 13) $.
Abbiamo conseguentemente:
$ A \equiv A \ (mod \ 13), 12B \equiv 12B \ (mod \ 13), $
$ 12^2C \equiv C \ (mod \ 13), 12^3D \equiv 12D \ (mod \ 13), $ etc. Sommando tutte le congruenze otteniamo, indicando con $ S_p $ la somma delle cifre di posto pari e con $ S_d $ la somma delle cifre di posto dispari, $ n\equiv S_d+12S_p \equiv S_d+13S_p-S_p \equiv S_d-S_p \ (mod \ 13) $. Ne viene la tesi.
La congruenza non dipende dalla base di numerazione scelta per il fatto che un numero resta sempre se stesso, anche in un'altra base. La base di numerazione influisce solamente sul modo di scriverlo. E' questo il motivo...Zok?
Scriviamo $ n $ in forma polinomiale: $ n=A+12B+12^2C+12^3D+12^4E+... $
DIVISIBILITA' PER 3
$ n $ è divisibile per $ 3 $ se e solo se la sua ultima cifra è divisibile per $ 3 $.
Se $ A $ è divisibile per $ 3 $ allora anche $ n $ lo è. In caso contrario $ 3 $ divide tutti e soli i fattori diversi da $ A $, e ciò implica che $ n $ non è divisibile per $ 3 $.
DIVISIBILITA' PER 11
$ n $ è divisibile per $ 11 $ se e solo se la somma delle sue cifre è divisibile per $ 11 $.
Dimostriamo intanto per induzione che $ 12^k\equiv 1 \ (mod \ 11) $ ($ k>0 $). Per $ k=1 $ abbiamo $ 12\equiv 1 \ (mod \ 11) $, vero perchè $ 12-1=11=1\cdot 11 $. Supponiamo la tesi vera per $ k=h $, ovvero $ 12^h\equiv 1 \ (mod \ 11) $, moltiplichiamo per $ 12 $ entrambi i membri della congruenza ottenendo $ 12^{h+1}\equiv 12\equiv 1 \ (mod \ 11) $.
Abbiamo conseguentemente:
$ A\equiv A \ (mod \ 11), 12B\equiv B \ (mod \ 11), 12^2C\equiv C \ (mod \ 11), $ etc. Sommando tutte le congruenze otteniamo $ n\equiv S \ (mod \ 11) $, dove $ S $ è la somma delle cifre di $ n $. Ne viene la tesi.
DIVISIBILITA' PER 13
$ n $ è divisibile per $ 13 $ se e solo se il valore assoluto della differenza tra la somma delle cifre di posto pari e la somma delle cifre di posto dispari è divisibile per $ 13 $.
Dimostriamo intanto per induzione che $ 12^{2k}\equiv 1 \ (mod \ 13) $ ($ k>0 $). Per $ k=1 $ abbiamo $ 144\equiv 1 \ (mod \ 13) $, vero perchè $ 144-1=11\cdot 13 $. Supponiamo la tesi vera per $ k=h $, ovvero $ 12^{2h}\equiv 1 \ (mod \ 13) $, moltiplichiamo per $ 12^2 $ entrambi i membri della congruenza ottenendo $ 12^{2(h+1)}\equiv 12^2\equiv 1 \ (mod \ 13) $.
Ora ci serve dimostrare che $ 12^{2k+1}\equiv 12 \ (mod \ 13) $ ($ k>0 $). Per $ k=1 $ abbiamo $ 12^3\equiv 12 \ (mod \ 13) $, vero perchè $ 1728-12=132\cdot 13 $. Supponiamo la tesi vera per $ k=h $, ovvero $ 12^{2h+1}\equiv 12 \ (mod \ 13) $, moltiplichiamo per $ 12^2 $ entrambi i membri della congruenza ottenendo $ 12^{2(h+1)+1}\equiv 12^3\equiv 12 \ (mod \ 13) $.
Abbiamo conseguentemente:
$ A \equiv A \ (mod \ 13), 12B \equiv 12B \ (mod \ 13), $
$ 12^2C \equiv C \ (mod \ 13), 12^3D \equiv 12D \ (mod \ 13), $ etc. Sommando tutte le congruenze otteniamo, indicando con $ S_p $ la somma delle cifre di posto pari e con $ S_d $ la somma delle cifre di posto dispari, $ n\equiv S_d+12S_p \equiv S_d+13S_p-S_p \equiv S_d-S_p \ (mod \ 13) $. Ne viene la tesi.
La congruenza non dipende dalla base di numerazione scelta per il fatto che un numero resta sempre se stesso, anche in un'altra base. La base di numerazione influisce solamente sul modo di scriverlo. E' questo il motivo...Zok?
"Il fatto che un'opinione sia ampiamente condivisa, non è affatto una prova che non sia completamente assurda" B. Russell