Aritmetica modulare: criteri di divisibilità

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Aritmetica modulare: criteri di divisibilità #4941

avt
Davidesaf
Punto
Salve! Ho problemi a risolvere questo esercizio di aritmetica modulare sui criteri di divisibilità.

Dedurre utilizzando l'aritmetica modulare un criterio di divisibilità per 69 ed applicarlo ai seguenti numeri. 86526 e 90562.

Vorrei capire il procedimento. So che bisogna utilizzare i moduli ma non riesco a trovare criterio generale! Vi prego aiutatemi!
 
 

Aritmetica modulare: criteri di divisibilità #4944

avt
frank094
Maestro
Ciao Davidesaf, la prima cosa che possiamo fare è prendere 69 e scomporlo come prodotto di numeri primi per semplificare il più possibile il lavoro.

69 = 3 \cdot 23

Dobbiamo fermarci ma abbiamo già fatto una notevole semplificazione: un numero è divisibile per 69 se e solo se è divisibile sia per 3 che per 23 .. ossia deve valere il sistema

\left \{ \begin{matrix} n \equiv_3 0 \\ n \equiv_{23} 0 \end{matrix}

Un numero è divisibile per 23 solo sotto determinate condizioni: se n è divisibile per 23 allora anche la somma fra il numero, privato della cifra delle unità, e il settuplo dell'unità è divisibile per 23.
Dimostrerò tale criterio per numeri di tre cifre ma seguendo lo stesso metodo puoi farlo con grande facilità anche per numeri di 6 cifre e, perché no, generalizzare.

Dimostrazione: Dato il numero n = 10^2 a + 10^1 b + 10^0 c supponiamo che valga la seguente relazione

23 \mbox{ } | \mbox{ } n \to 23 \mbox{ } | \mbox{ } 100a + 10b + c

allora dobbiamo dimostrare che

23 \mbox{ } | \mbox{ } 10a + b + 7c

Partiamo dalla relazione principale

23 \mbox{ } | \mbox{ } 100a + 10b + c \to 23 \mbox{ } | \mbox{ } 100a + 10b + c - 23(4a + 4b + 4c)

23 \mbox{ } | \mbox{ } 100a + 10b + c \to 23 \mbox{ } | \mbox{ } 8a - 82b - 91c

23 \mbox{ } | \mbox{ } 8a - 82b - 91c \to 23 \mbox{ } | \mbox{ } 8a - 82b - 91c + 23(4b + 7c)

23 \mbox{ } | \mbox{ } 8a + 10b + 70c + 23(4a)

23 \mbox{ } | \mbox{ } 100a + 10b + 70c

23 \mbox{ } | \mbox{ } 10a + b + 7c

Ed ecco finita la dimostrazione. Nei vari passaggi non ho specificato molto perché ho fatto solo delle somme "ad istinto" seguendo la regola per cui

a \mbox{ } | \mbox{ } b \Longleftrightarrow a \mbox{ } | \mbox{ } b \pm na \qquad n \in \mathbb{N}

Abbiamo quindi dimostrato che un numero è divisibile per 69 se e solo se la somma delle sue cifre torna un multiplo di 3 e la somma del numero privato delle unità con il settuplo delle unità torna un numero divisibile per 23 ( e iterando il processo si va ).
Applichiamolo ai tuoi due esempi:

86526 \equiv_3 (8 + 6 + 5 + 2 + 6) \equiv_3 27 \equiv_3 0

La prima condizione è verificata. Vediamo la seconda ..

86526 \equiv_{23} (8652 + 7 \cdot 6) \equiv_{23} 8694 \equiv_{23} 869 + 28 \equiv_{23} 897 \equiv_{23} 0

La seconda condizione è verificata e il numero è divisibile per 69! Il secondo vuoi provare tu?
Ringraziano: Omega, Pi Greco, Ifrit

Aritmetica modulare: criteri di divisibilità #5014

avt
Davidesaf
Punto
Grazie mille della risposta tempestiva! Ho capito quasi tutto, l'unico problema è che non riesco a trovare un sistema meccanico per calcolarlo.

Allora andando passo passo. Faccio un esempio con 77.

Divido il numero in fattori primi. e quindi un numero è divisibile solo se è divisibile sia per 7 e sia per 11. E poi non riesco a trovare il criterio generale. E sopratutto non riesco a fare la dimostrazione.

Sono disperato...

Aritmetica modulare: criteri di divisibilità #5139

avt
frank094
Maestro
Perdona il ritardo nella risposta ma ho avuto parecchio da fare e non ho avuto modo di collegarmi emt

I criteri generali dei numeri primi si trovano senza problemi su di un qualsiasi libro, anche delle elementari. Ad esempio qui su YouMath c'è una validissima lezione dedicata alle scuole medie (criteri di divisibilità).

La parte bella e più universitaria è dimostrarlo. Magari provo con un'altra dimostrazione e vediamo cosa ci esce.

Criterio 7: un numero è divisibile per 7 se e solo se lo è anche il numero privato della cifra delle unità e diminuito del doppio di questa.

Dimostrazione: sia a un numero divisibile per 7 tale che può essere scritto come

a = 10q + r \qquad 0 \leq r < 10

dobbiamo dimostrare semplicemente che lo è anche b = q - 2r. Questo perché r rappresenta le unità quindi il numero q è quello privato di quest'ultima.

Poiché a è un numero divisibile per 7 allora possiamo scrivere senza problemi che

7m = 10q + r \qquad m \in \mathbb{N}

r = 7m - 10q \qquad m \in \mathbb{N}

Andiamo a sostituire questa relazione in quella da dimostrare in modo da ottenere

b = q - 2\cdot(7m - 10q)

b = 21q - 14m

b = 7 \cdot (3q - 2m)

Il numero risulta dunque divisibile per 7. Adesso ti basta dimostrare che partendo da b allora anche a è divisibile per 7.

Criterio 11: un numero naturale a è divisibile per 11 se e solo se la somma con segni alterni delle cifre in base 10 è un numero divisibile per 11.

Vuoi provare tu a dimostrarlo? Ti conviene farlo per numeri di cifre limitate, in tal modo è molto facile.
Ringraziano: Omega, Pi Greco, Davidesaf

Aritmetica modulare: criteri di divisibilità #5164

avt
Davidesaf
Punto
Grazie mille molto gentile! Sta a me ora capirlo ed applicarlo a più numeri! Grazie ancora!
Ringraziano: frank094
  • Pagina:
  • 1
Os