OliForum Matematico

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.

Ci provo... 625? Se è corretto posto anche la mia spiegazione (dopo averla riordinata un po' )

no, va bene così, xo rispondi anche a questa che ho risolto ieri notte a mente..
e la congruenza modulo 10^6?

jordan ha scritto:no, va bene così, xo rispondi anche a questa che ho risolto ieri notte a mente..
e la congruenza modulo 10^6?

Edit: stupidaggine, grazie Jordan

Ale90 saresti così gentile da spiegare anche come trovarlo

Juggler ha scritto:Ale90 saresti così gentile da spiegare anche come trovarlo

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 mente

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*

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!)

jordan 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!)

Sì giusto, e dire che ci avevo anche pensato
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

guarda per farlo a mente devi farlo cifra per cifra, modulo 5 e 2, 25 e 4, 125 e 8 e e infine 625 e 16 per le ultime 4 cifre..la strada poi èla stessa ma i conti si complicano..buon appetito cmq

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

Ma perché 'sta roba sta in combinatoria???
Lo sposto immediatamente in teoria dei numeri ... non me ne ero accorto prima. Sorry

ehm....scusate tanto, avete ragione.
cmq x ale 90 perfetto , modulo 10^5 è 40625