Olimpiadi della Matematica Torino - OliMaTO - Forum

Buone feste a tutti ! Scrivo questo post riguardo all'aritmetica modulare per avere delucidazioni sul calcolo di un generale N mod m ( con m non notevole tipo 3,9,11,5 2^n o altro). Ad esempio un numero di molte cifre modulo 900 o anche altre (mod p×q×t×s) con p,q,t,s primi! Come si fa a calcolare velocemente il modulo? Io ad esempio per mod15 avevo calcolato che essendo il mio n congruo 4 (mod5) allora n (mod 15) doveva essere un 4+k5 ma visto che n era divisibile per 3 lo doveva essere anche 4+k5 per mantenere inalterata la divisibilita per 3. Però quando trovo un 7 o un qualsiasi numero non "notevole" cosa mi invento visto che non esistono trucchi di divisibilita e resto o sono molto complicati e magari non criteri di congruenza (vedi il 7) ? Grazie mille veramente e buone feste ancora!!

Alla fine mi convincerò che non esiste

Volendo puoi trovare criteri di congruenza per ogni modulo, scrivi il numero in notazione polinomiale (come p(10) del polinomio che ha le sue cifre come coefficienti) e fai 10 modulo m ogni volta dove compare...

afullo ha scritto:Volendo puoi trovare criteri di congruenza per ogni modulo, scrivi il numero in notazione polinomiale (come p(10) del polinomio che ha le sue cifre come coefficienti) e fai 10 modulo m ogni volta dove compare...

Ah quindi trasformeresti il numero n [tratto da n(mod m) ]in una somma e poi applicheresti modulo m a ogni termine dell addizione per la regola che a+b+c (mod m) = d+e+f (mod m) con a congruo d, b congruo e, e c congruo f?
Grazie afullo

Esatto, e fai lo stesso prima per i prodotti tra cifra e potenza di 10 corrispondente...

Grazi afullo ci testerò qualche problemetto arzigogolato... buone feste

Puoi dimostrare che le cifre le moltiplichi sempre per quantità <= m/2, quindi ti restano numeri piccoli. Buone feste anche a te!