voi come lo risolvereste? (congruenze)
$ \dispaystyle \\
9^{15} \equiv x \pmod{37}\\
(9^{5})^{3} \equiv x \pmod{37}\\
(34)^{3} \equiv x \pmod{37}\\
10 \equiv x \pmod{37}\\
$
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
dopo estenuanti calcoli (certo che son proprio a terra con le congruenze, daltronde le conosco da poco)...
Sono arrivato anche io a canclusione che il risultato è 10
Non sò se il testo dà un risultato sbagliato...ma dato che a molti utenti viene 10 come risultato...
Va bè...
Spero si chiarisca la cosa...
Sono arrivato anche io a canclusione che il risultato è 10
Non sò se il testo dà un risultato sbagliato...ma dato che a molti utenti viene 10 come risultato...
Va bè...
Spero si chiarisca la cosa...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Ragazzi ... tre pagine per fare un conto?? Suvvia ... non c'è ancora stato uno che abbia postato la soluzione nei dettagli di modo che gli altri possano convincersi non per l'autorità della fonte ma semplicemente perchè è giusto...non si fa così.
Dovete anche imparare a fare i conti furbamente:
$ (102^{73}+55)^{87}\equiv x\ \bmod\ 111 $
si riscrive come
$ \left\{\begin{array}{cccc}(102^{73}+55)^{87}&\equiv&x&(3)\\ (102^{73}+55)^{87}&\equiv&x&(37)\end{array}\right. $
Ora, per la prima si ha $ 102\equiv 0\mod 3 $ e $ 55\equiv 1\mod 3 $ da cui si ricava $ x\equiv 1\mod 3 $.
Per la seconda, $ 102\equiv -9 \mod 37 $ (102=111-9) e $ 55\equiv18\mod 37 $. Inoltre, per il piccolo teorema di Fermat $ a^{36}\equiv 1\mod 37 $ (se a non è nullo) e dunque $ (-9)^{73}\equiv(-9)\mod 37 $.
Quindi $ (102^{73}+55)\equiv 9\mod 37 $. Infine $ 9^{87}\equiv 9^{15}\mod 37 $.
Risolvendo la prima congruenza, $ x=3y+1 $ e sostituendo nella seconda
$ 3y\equiv 9^{15}-1\mod 37 $
ovvero
$ 3y\equiv (9^3-1)(9^{12}+9^{9}+9^{6}+9^3+1) \mod 37 $
Ora $ 9^3=729=666+37+26\equiv 26\mod 37 $.
Inoltre $ (26)^2\equiv(-11)^2\equiv121\equiv 10\mod 37 $.
Quindi $ (9^3)^2+9^3+1\equiv 10+26+1\equiv 0\mod 37 $.
Ancora, $ (26)^3\equiv10(-11)\equiv 1\mod 37 $, quindi
$ 9^9(9^3+1)\equiv9^3+1\equiv -10\mod 37 $.
In conclusione $ 3y\equiv 120\mod 37 $ ovvero $ y\equiv 40\mod 37 $ ovvero $ y\equiv 3\mod 37 $ da cui $ x=3(3+37k)+1=10+111k $.
Dovete anche imparare a fare i conti furbamente:
$ (102^{73}+55)^{87}\equiv x\ \bmod\ 111 $
si riscrive come
$ \left\{\begin{array}{cccc}(102^{73}+55)^{87}&\equiv&x&(3)\\ (102^{73}+55)^{87}&\equiv&x&(37)\end{array}\right. $
Ora, per la prima si ha $ 102\equiv 0\mod 3 $ e $ 55\equiv 1\mod 3 $ da cui si ricava $ x\equiv 1\mod 3 $.
Per la seconda, $ 102\equiv -9 \mod 37 $ (102=111-9) e $ 55\equiv18\mod 37 $. Inoltre, per il piccolo teorema di Fermat $ a^{36}\equiv 1\mod 37 $ (se a non è nullo) e dunque $ (-9)^{73}\equiv(-9)\mod 37 $.
Quindi $ (102^{73}+55)\equiv 9\mod 37 $. Infine $ 9^{87}\equiv 9^{15}\mod 37 $.
Risolvendo la prima congruenza, $ x=3y+1 $ e sostituendo nella seconda
$ 3y\equiv 9^{15}-1\mod 37 $
ovvero
$ 3y\equiv (9^3-1)(9^{12}+9^{9}+9^{6}+9^3+1) \mod 37 $
Ora $ 9^3=729=666+37+26\equiv 26\mod 37 $.
Inoltre $ (26)^2\equiv(-11)^2\equiv121\equiv 10\mod 37 $.
Quindi $ (9^3)^2+9^3+1\equiv 10+26+1\equiv 0\mod 37 $.
Ancora, $ (26)^3\equiv10(-11)\equiv 1\mod 37 $, quindi
$ 9^9(9^3+1)\equiv9^3+1\equiv -10\mod 37 $.
In conclusione $ 3y\equiv 120\mod 37 $ ovvero $ y\equiv 40\mod 37 $ ovvero $ y\equiv 3\mod 37 $ da cui $ x=3(3+37k)+1=10+111k $.
Ma no, non puoi fermarti davanti a così poco... Un conto è fare una faccia schifata di fronte al coseno modulo p, ma invertire mod 3 è lecito (sempre che non si divida per 0...)julio14 ha scritto:Per esempio 10/2 non è congruo a 1/2 mod3
Comunque, per semplificare ulteriormente i conti uno poteva notare che $ 9^4\equiv 12\equiv \frac{-1}{3}\pmod{37} $, trovando cosi che $ 3^9=-1 $, da cui $ 3^{174}=3^{12}=-3^3=-27=10 $
"Sei la Barbara della situazione!" (Tap)
piever ha scritto:Ma no, non puoi fermarti davanti a così poco... Un conto è fare una faccia schifata di fronte al coseno modulo p, ma invertire mod 3 è lecito (sempre che non si divida per 0...)
Si in effetti mi sono fermato un po' presto... ma non sono la persona più indicata per dare lezioni di teoria, volevo solo evitare che angus89 dividesse così a casaccio
Magari la pensassero tutti così...EvaristeG ha scritto:Ragazzi ... tre pagine per fare un conto?? Suvvia ... non c'è ancora stato uno che abbia postato la soluzione nei dettagli di modo che gli altri possano convincersi non per l'autorità della fonte ma semplicemente perchè è giusto...non si fa così.
Comunque ormai ieri ci ho perso mezz'ora...anche se sbattere un pò la testa magari mi è anche stato utile...
grazie mille comunque...
io comunque per risolvere il tutto mi sono rifatto alla soluzione delle diofantee nella forma
$ \dispaystyle \\ ax-by=c \\ c=k \cdot MCD(a,b) $
ovvero dove c è multiplo del massimo comune divisore di a e b
Ora mi vedo anche il metodo di EvaristeG
Ultima modifica di angus89 il 18 feb 2008, 18:00, modificato 1 volta in totale.
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
-
matemark90
- Messaggi: 67
- Iscritto il: 03 nov 2006, 20:02
- Località: la città del carnevale (RE)
Anche se è inutile vorrei precisare che il risultato del libro è corretto... E' sbagliato il testo. Non so se è stata una vista di Angus o un errore di stampa comunque io ho il Davenport e il testo è $ (102^{73}+55)^{37}\equiv x(mod111) $
E in effetti risulta proprio 46.
poi certo, un po' di calcoli intelligenti non fanno mai male
E in effetti risulta proprio 46.
poi certo, un po' di calcoli intelligenti non fanno mai maleHasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
onde evitare di fare la figura del deficiente...matemark90 ha scritto:Anche se è inutile vorrei precisare che il risultato del libro è corretto... E' sbagliato il testo. Non so se è stata una vista di Angus o un errore di stampa comunque io ho il Davenport e il testo è $ (102^{73}+55)^{37}\equiv x(mod111) $
E in effetti risulta proprio 46.
Il mio testo è fotocopiato (sempre con le normative del copyright)...e la sbavatura mi ha fatto legger male...se non avessi corretto tu sarei ancora convinto che fosse 87...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Ciao! Mi sono improvvisamente reso conto di quanto poco ne sappia in materia di congruenze...c'è qualche libro o qualunque altra fonte che sia illuminante in materia (con tanto di esercizi svolti o qualcosa del genere)? perchè guaradando qua e là nel sito qualcosa si coglie ma ho idea che siano cose piuttosto frammentarie...
Grazie..
Grazie..
(no comment)
dispense
Ce ne sono molte in internet...guarda un pò sempre sul forum....
Ce ne sono molte in internet...guarda un pò sempre sul forum....
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
comunque ti consiglio vivamente di fare gli esercizi di massimo gobbino...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
