Fattoriale dispari
Fattoriale dispari
Calcolare le ultime quattro cifre del numero:
$ 1\cdot 3\cdot 5\cdot ... \cdot9997\cdot 9999 $
Io l'ho fatto, ma forse con un sistema un po' lungo. Probabilmente c'è un metodo più furbo, che mi è sfuggito.
$ 1\cdot 3\cdot 5\cdot ... \cdot9997\cdot 9999 $
Io l'ho fatto, ma forse con un sistema un po' lungo. Probabilmente c'è un metodo più furbo, che mi è sfuggito.
Re: Fattoriale dispari
Se intendi le ultime quattro cifre a destra è semplice 0000.Cammy87 ha scritto:Calcolare le ultime quattro cifre del numero:
$ 1\cdot 3\cdot 5\cdot ... \cdot9997\cdot 9999 $
Io l'ho fatto, ma forse con un sistema un po' lungo. Probabilmente c'è un metodo più furbo, che mi è sfuggito.
Ah che distratto, il fattoriale è dispari...
Calcolo l'ultima cifra (quella più a destra?) abbiamo
$ 1\cdot 3\cdot 5\cdot7\cdot 9 \-= 5 \mod 10 $
essendo $ 5^n \-= 5 \mod 10 \forall n \in N^+ $ l'ultima cifra è 5.
Salute a tutti, sono nuovo
Dunque, il numero termina socuramente per 5 poichè è un multiplo dispari di 5 (è sempre assente il fattore 2).
Dunque
(scusate ma sto ancora prendendo familiarità col latex)
$ 1*3*5*...*9999 $ è come scrivere $ \frac{10000!}{2*4*6*...*10000} $
Il valore 10000! mi aspetto che abbia 1000 zeri poichè ci sono 1000 multipli di 10, da cui 1000 2*5
Tutti i 2 vengono semplificati nella frazione e resta dunque $ 5^{1000}. $
Mi accorgo che tutte le potenze pari di 5 terminano con 25 (la seconda) e poi con 625 (dalla quarta in su),
quindi il nuumero terminerà con 625.
La quarta cifra credo si possa trovare allo stesso modo ma non ho verificato
Dunque, il numero termina socuramente per 5 poichè è un multiplo dispari di 5 (è sempre assente il fattore 2).
Dunque
(scusate ma sto ancora prendendo familiarità col latex)
$ 1*3*5*...*9999 $ è come scrivere $ \frac{10000!}{2*4*6*...*10000} $
Il valore 10000! mi aspetto che abbia 1000 zeri poichè ci sono 1000 multipli di 10, da cui 1000 2*5
Tutti i 2 vengono semplificati nella frazione e resta dunque $ 5^{1000}. $
Mi accorgo che tutte le potenze pari di 5 terminano con 25 (la seconda) e poi con 625 (dalla quarta in su),
quindi il nuumero terminerà con 625.
La quarta cifra credo si possa trovare allo stesso modo ma non ho verificato
Se può essere utile $ 5^n $, se $ n\geq4 $ e $ 4|n $, finisce per 0625. Ma non riesco a capire (mea culpa, oppure culpa della verifica che non hai ancora fatto) perchè il fattoriale debba finire con 625: non è una potenza di 5. Dunque, perché dovrebbe finire per 625?
A proposito: benvenuto nel forum Martin!
A proposito: benvenuto nel forum Martin!
"Sei la Barbara della situazione!" (Tap)
$ 5^4=625 $ un piccolo errore di calcolo, tutto qui...piever ha scritto:Se può essere utile $ 5^n $, se $ n\geq4 $ e $ 4|n $, finisce per 0625. Ma non riesco a capire (mea culpa, oppure culpa della verifica che non hai ancora fatto) perchè il fattoriale debba finire con 625: non è una potenza di 5. Dunque, perché dovrebbe finire per 625?
A proposito: benvenuto nel forum Martin!
Ciao Ciao
-
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Beh, dico anch'io la mia. Chiedere le ultime quattro cifre equivale a chiedere la congruenza modulo 10000, ossia $ 2^4*5^4 $
Modulo $ 5^4 $ questo numero è zero, in quanto ci sono ben più di quattro multipli di 5 nel prodotto
Per calcolare la congruenza modulo 16, invece, il mio procedimento è questo: divido i 5000 valori in gruppi da 8:
1-3-5-7-9-11-13-15
17-19-21-23-25-27-29-31
...
in cui compaiono tutte le classi di congruenza dispari modulo 16. Il prodotto dei termini in un gruppo è congruo (si verifica facilmente) a 1 modulo 16, quindi il prodotto di tutti i gruppi è congruo a 1 mod 16.
Detto questo, per il teorema cinese, sappiamo che esiste una sola soluzione modulo 10000 del sistema $ x \equiv 0 (\mod 5^4) $ e $ x \equiv 1 (\mod 16) $. Si verifica facilmente che $ 625 \equiv 1 (\mod 16) $ e quindi abbiamo trovato la nostra soluzione: 0625.
Ciao!
Modulo $ 5^4 $ questo numero è zero, in quanto ci sono ben più di quattro multipli di 5 nel prodotto
Per calcolare la congruenza modulo 16, invece, il mio procedimento è questo: divido i 5000 valori in gruppi da 8:
1-3-5-7-9-11-13-15
17-19-21-23-25-27-29-31
...
in cui compaiono tutte le classi di congruenza dispari modulo 16. Il prodotto dei termini in un gruppo è congruo (si verifica facilmente) a 1 modulo 16, quindi il prodotto di tutti i gruppi è congruo a 1 mod 16.
Detto questo, per il teorema cinese, sappiamo che esiste una sola soluzione modulo 10000 del sistema $ x \equiv 0 (\mod 5^4) $ e $ x \equiv 1 (\mod 16) $. Si verifica facilmente che $ 625 \equiv 1 (\mod 16) $ e quindi abbiamo trovato la nostra soluzione: 0625.
Ciao!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
La tua risposta, darkcrystal, è giusta: il numero termina per 0625!!!!
Il tuo procedimento è anche molto più rapido del mio, seppur concettualmente simile.
Avevo trovato che il fattoriale doveva essere $ \equiv1\pmod{16} $ e$ \equiv0\pmod{5^4} $, ma per trovare il valore giusto ho dovuto controllare tutte le possibili terminazioni di un numero multiplo di $ 5^4 $, e vedere quali fossero effettivamente $ \equiv1\pmod{16} $.
Con il teorema cinese del resto si evitano un bel po' di conti e di divisioni.
Ciao ciao
Il tuo procedimento è anche molto più rapido del mio, seppur concettualmente simile.
Avevo trovato che il fattoriale doveva essere $ \equiv1\pmod{16} $ e$ \equiv0\pmod{5^4} $, ma per trovare il valore giusto ho dovuto controllare tutte le possibili terminazioni di un numero multiplo di $ 5^4 $, e vedere quali fossero effettivamente $ \equiv1\pmod{16} $.
Con il teorema cinese del resto si evitano un bel po' di conti e di divisioni.
Ciao ciao
La mia soluzione è simile alle vostre:
Innanzitutto, poiché all’interno della produttoria c’è il fattore 625, e 625*16=10000, ne consegue che gli unici modi in cui può terminare questo numero sono: 0625, 1250, 1875, 2500, 3125, 3750, 4375, 5000, 5625, 6250, 6875, 7500, 8125, 8750, 9375, 0000. Poiché però non sono presenti fattori pari, possiamo tranquillamente scartare le terminazioni pari: restano quindi 0625, 1875, 3125, 4375, 5625, 6875, 8125, 9375. Resta ora da determinare la congruenza modulo 16 del prodotto di tutti gli altri fattori. Ma 1*3*5*7*9*11*13*15 = 2.027.025 = 126.689*16+1, ovvero il prodotto è congruo a 1 modulo 16. Allora è congruo a 1 modulo 16 anche ogni prodotto del tipo (16n+1) * (16n+3) * (16n+5) * (16n+7) * (16n+9) * (16n+11) * (16n+13) * (16n+15). Facendo variare n fra 0 e 624 si ottengono tutti i fattori della produttoria considerata, che dunque è anch’essa congrua a 1 modulo 16. Dovevamo però determinare il resto della divisione modulo 16 di tutti i fattori escluso il 625; però questo è congruo a 1, quindi il quoziente è anch’esso congruo a 1. Di conseguenza possiamo affermare che il prodotto è della forma 625*(16m+1) = 10000*m+625, dunque il numero termina per 0625.
Innanzitutto, poiché all’interno della produttoria c’è il fattore 625, e 625*16=10000, ne consegue che gli unici modi in cui può terminare questo numero sono: 0625, 1250, 1875, 2500, 3125, 3750, 4375, 5000, 5625, 6250, 6875, 7500, 8125, 8750, 9375, 0000. Poiché però non sono presenti fattori pari, possiamo tranquillamente scartare le terminazioni pari: restano quindi 0625, 1875, 3125, 4375, 5625, 6875, 8125, 9375. Resta ora da determinare la congruenza modulo 16 del prodotto di tutti gli altri fattori. Ma 1*3*5*7*9*11*13*15 = 2.027.025 = 126.689*16+1, ovvero il prodotto è congruo a 1 modulo 16. Allora è congruo a 1 modulo 16 anche ogni prodotto del tipo (16n+1) * (16n+3) * (16n+5) * (16n+7) * (16n+9) * (16n+11) * (16n+13) * (16n+15). Facendo variare n fra 0 e 624 si ottengono tutti i fattori della produttoria considerata, che dunque è anch’essa congrua a 1 modulo 16. Dovevamo però determinare il resto della divisione modulo 16 di tutti i fattori escluso il 625; però questo è congruo a 1, quindi il quoziente è anch’esso congruo a 1. Di conseguenza possiamo affermare che il prodotto è della forma 625*(16m+1) = 10000*m+625, dunque il numero termina per 0625.
Ultima modifica di afullo il 07 apr 2006, 19:37, modificato 1 volta in totale.
Le ultime cifre di un numero si determinano con le congruenze in quanto l'ultima cifra di un numero è pari alla congruenza modulo 10 di quel numero, le ultime due cifre sono pari alla congruenza modulo 100, le ultime tre alla congruenza modulo 1000... le ultime n alla congruenza modulo 10^n.
tutto chiaro adesso?
tutto chiaro adesso?