Questa è TdN, non combinatoria... -- Sam
determinare la classe di resto modulo 10^4 della produttoria degli (2i-1) per i che va da 1 a 5000.
produttoria
Edit: stupidaggine, grazie Jordanjordan ha scritto:no, va bene così, xo rispondi anche a questa che ho risolto ieri notte a mente..
e la congruenza modulo 10^6?
Ultima modifica di Ale90 il 20 lug 2007, 19:23, modificato 1 volta in totale.
Faccio il caso 10^4 perché l'altro è più brutto e contoso... anche se evidentemente c'è una soluzione molto più rapida, visto che Jordan l'ha risolto a menteJuggler ha scritto:Ale90 saresti così gentile da spiegare anche come trovarlo
All'interno della produttoria (di numeri dispari) abbiamo un fattore 625: questo implica che il resto modulo 10^4 non possa che essere uno tra 625, 625*3, 625*5, 625*7... 625*15 [dopo infatti si ripetono ciclicamente].
Abbiamo quindi:
$ 1 \cdot 3 \cdot 5 \cdot 7 \cdot ... \cdot 625 \cdot ... \cdot 9997 \cdot 9999 = 625k \pmod{16 \cdot 625} $
Dividiamo tutto per 625 e vediamo che il problema si è ridotto a trovare la congruenza della produttoria (diviso 625) modulo 16.
$ 1 \cdot 3 \cdot 5 \cdot 7 \cdot ... \cdot 625 \cdot ... \cdot 3123 \cdot 5 \cdot 3127 \cdot ... \cdot 9999 = k \pmod{16} $
(Ho preferito rimuovere il 625 da 3125 lasciando 5).
I numeri dispari possono essere congrui a $ \pm 1 \pmod{4} $: se ne prendiamo due consecutivi del tipo 4k-1 e 4k+1 (quindi con ugual k) e li moltiplichiamo otteniamo un numero congruo a $ -1 \pmod{16} $, infatti $ (4k-1)(4k+1)=16k^2-1 $.
A questo punto raggruppiamo a coppie (partendo da 3 e 5) tutti i numeri della produttoria escluso 1 che tanto non dà problemi: ogni coppia ci fornisce un fattore moltiplicativo -1 modulo 16, compresa (3123, 5) che però va controllata a mano. Si vede che la coppia 9995, 9997 è l'ultima: rimane "spaiato" 9999, che è congruo a $ -1 \pmod{16} $ [è 10000 meno 1].
Quante sono le coppie da (3,5) a (9995, 9997) comprese? Esattamente 2499.
La congruenza totale modulo 16 è quindi $ (-1)^{2499+1} = 1 $.
Il problema chiedeva la congruenza modulo 10000, che è quindi 625 * 1 = 625.
*Dimostrazione più brutta del secolo*
Sì giusto, e dire che ci avevo anche pensatojordan ha scritto:x ale90..la classe di congruenza di P modulo 10^4 è 625. allora è giusto se dico ke modulo 10^6 è ab0625 (in notazione decimale) con a,b in [0,9] ?ricontrolla il tuo risultato...(cmq si risolve a mente anche con 10^5 e 10^6 anche se è abbastanza piu difficile!)
Ma quando sono arrivato in fondo non avevo più la forza di decifrare quello che avevo scritto
Ma il caso 10^4 l'hai fatto come me o mi sono complicato la vita? Propendo per la seconda ipotesi
Comunque è vero, una volta trovato 0625 gli altri sono abbastanza facili, basta ragionare sulle possibilità e andare per esclusione, direi: dopo cena mi ci metto un attimo e ti faccio sapere
Allora...
Proviamo con 10^5.
Il ragionamento contorto di qualche post fa porta, per motivi analoghi, ad avere che
$ 1 \cdot 3 \cdot 5 \cdot 7 \cdot ... \cdot 3125 \cdot ... \cdot 9997 \cdot 9999 = 3125k \pmod{32 \cdot 3125} $
Dividiamo tutto per 3125 e andiamo a cercare la congruenza modulo 32.
A questo punto notiamo una cosa carina: se prendiamo due numeri della forma 4k+1 e 4k+3 e li moltiplichiamo, essi daranno sempre resto 3 se divisi per 32. Perché? $ (4k+1)(4k+3)=16k^2+16k+3=16k(k+1)+3 $, quindi uno tra k e k+1 sarà pari e renderà il tutto della forma 32j+3
Abbiamo quindi 2499 coppie che danno fattori 3 e il 3127 rimasto spaiato che dà un fattore 23.
Di conseguenza la congruenza modulo 32 è data da $ 3^{2499}*23 $.
Ora, dato che $ 3^8 = 1 \pmod{32} $, $ 3^{2499} $ è congruo a $ 3^3 $ (2496 è divisibile per 8). La congruenza modulo 32 è quindi data da $ 3^3*23 = 13 \pmod{32} $.
Di conseguenza modulo 10^5 abbiamo 3125*13 = 40625 (che rispetta quanto trovato in precedenza; per la cronaca l'unico altro resto possibile modulo 32 sarebbe stato 29, che avrebbe dato 90625).
Il 10^6 lo lascio a qualcun altro se ne ha voglia... io sono stanco e ho già fatto abbastanza figuracce per oggi
Proviamo con 10^5.
Il ragionamento contorto di qualche post fa porta, per motivi analoghi, ad avere che
$ 1 \cdot 3 \cdot 5 \cdot 7 \cdot ... \cdot 3125 \cdot ... \cdot 9997 \cdot 9999 = 3125k \pmod{32 \cdot 3125} $
Dividiamo tutto per 3125 e andiamo a cercare la congruenza modulo 32.
A questo punto notiamo una cosa carina: se prendiamo due numeri della forma 4k+1 e 4k+3 e li moltiplichiamo, essi daranno sempre resto 3 se divisi per 32. Perché? $ (4k+1)(4k+3)=16k^2+16k+3=16k(k+1)+3 $, quindi uno tra k e k+1 sarà pari e renderà il tutto della forma 32j+3
Abbiamo quindi 2499 coppie che danno fattori 3 e il 3127 rimasto spaiato che dà un fattore 23.
Di conseguenza la congruenza modulo 32 è data da $ 3^{2499}*23 $.
Ora, dato che $ 3^8 = 1 \pmod{32} $, $ 3^{2499} $ è congruo a $ 3^3 $ (2496 è divisibile per 8). La congruenza modulo 32 è quindi data da $ 3^3*23 = 13 \pmod{32} $.
Di conseguenza modulo 10^5 abbiamo 3125*13 = 40625 (che rispetta quanto trovato in precedenza; per la cronaca l'unico altro resto possibile modulo 32 sarebbe stato 29, che avrebbe dato 90625).
Il 10^6 lo lascio a qualcun altro se ne ha voglia... io sono stanco e ho già fatto abbastanza figuracce per oggi