OliForum Matematico

Come vi avevo preannunciato sono un nabbo nella teoria dei numeri, ho iniziato oggi a studiare le dispense olimpioniche linkatemi da Drago96 (che ringrazio).

Stavo facendo gli esercizi che ci sono in fondo e ce ne sono due che non mi tornano, qualcuno di voi può illustrarmi il procedimento per favore? Grazie...

Allora devo calcolare il modulo di:

35461^54593428 mod 11

tra le cose che ho finora studiato ho pensato alle operazioni ripetute, ma per trovare ogni quanto si ripete l'unico modo che conosco è calcolare il resto di al massimo 12 ripetizioni, ma data la grandezza del numero ci deve essere un altro metodo.

poi devo calcolare (353094232 mod 721)mod 9 e qui boh, ho provato a scomporre il 721 ma viene comunque (353094232 mod 7 * 353094232 mod 103) mod 9, che mi risulta comunque difficile

Mi date una mano? Grazie

Jona->PyLinX ha scritto:Allora devo calcolare il modulo di:

35461^54593428 mod 11

tra le cose che ho finora studiato ho pensato alle operazioni ripetute, ma per trovare ogni quanto si ripete l'unico modo che conosco è calcolare il resto di al massimo 12 ripetizioni, ma data la grandezza del numero ci deve essere un altro metodo.

E c'è...
L'elevamento a potenza è solo una moltiplicazione ripetuta, e come mi pare ci sia scritto, se devi calcolare $a\cdot b \mod x$, basta che fai prima il modulo di $a$, poi quello di $b$ e moltiplichi.
In questo caso calcoli $35461\mod11$ (che non è difficile, basta fare la somma delle cifre a segni alterni) e poi vedi come si ripetono le potenze del numero che ti viene modulo 11; conti quanto dura il "ciclo" e fai l'esponente modulo questo numero. A qusto punto non è poi troppo difficile fare il conto, spezzandolo.

Jona->PyLinX ha scritto:poi devo calcolare (353094232 mod 721)mod 9 e qui boh, ho provato a scomporre il 721 ma viene comunque (353094232 mod 7 * 353094232 mod 103) mod 9, che mi risulta comunque difficile

Quello che hai fatto è sbagliato: non puoi spezzare il modulo; se devi calcolare mod $x$, calcoli mod $x$.
In questo caso, direi che l'unico metodo è la divisione euclidea...
Per il mod 9 finale, ti basta fare la somma delle cifre...

Rimuginandoci ieri a cena alla prima c'ero arrivato. La seconda mi ero accorto di aver scomposto in un modo obrobrioso...Vabbè, era la prima volta che usavo il modulo. Devo guardarmi 'sta divisione euclidea

Jona->PyLinX ha scritto:Devo guardarmi 'sta divisione euclidea

E' semplicemente la divisione con resto...

Quella che afferma che per ogni coppia di interi $a,b$ esistono e sono unici $q,r$ tali che $a=b\cdot q+r$, con $0\leq r <| b|$

Detto banalmente: la divisione che facevi alle elementari

lol