OliForum Matematico

$ \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}\\ $

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...

Spesso i testi sbagliano, inoltre come ho già detto era un errore prevedibile che ha fatto anche shade, e dà ragione a noi anche il computer di darkcrystal... non credo ci siano dubbi

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 $.

julio14 ha scritto:Per esempio 10/2 non è congruo a 1/2 mod3

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

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 $

premetto che io non sono un grande esperto di congruenze, pero' da buon informatico ho calcolato il risultato e confermo 10! se vi interessa posto il codice...

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

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ì.

Magari la pensassero tutti 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

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

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. poi certo, un po' di calcoli intelligenti non fanno mai male

onde evitare di fare la figura del deficiente...

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...

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..

dispense
Ce ne sono molte in internet...guarda un pò sempre sul forum....

Mi è venuto in mente che un bel po' di tempo fa fph ebbe una grande idea, cerca un po' lì, qualcosa dovresti trovarci

comunque ti consiglio vivamente di fare gli esercizi di massimo gobbino...

Grazie 1000 a entrambi!!! ...(e anche a fph)

Anche se mi viene un po' l'angoscia a leggere tutta quella roba in inglese..

Buona Notte..