Finn x mod

[Nebuchadnezzar]

Er likningen under løsbar?

[tex]x^2 \equiv 17 \text{mod}(71)[/tex]

Vet ikke helt hvor jeg skal begynne.

[Gustav]

Beregn Legendre-symbolet [tex](17|71)=17^{35}\, mod(71)[/tex]. Antallet løsninger er [tex]1+(17|71)\,mod(71)[/tex]

http://en.wikipedia.org/wiki/Quadratic_ ... uare_roots

[Janhaa]

jeg veit generelt ikke hvordan kvadratiske modulo løses, men det blir vel

[tex]\frac{x^2-17}{71}\, \notin \, \mathbb{Z}[/tex]

den har vel ingen løsninger...?

[Nebuchadnezzar]

Dersom [tex]x[/tex] ikke var kvadrert ville den da hatt noen løsninger? Er det noen som vet hvordan slike oppgaver løses? Prøvde å søke litt på nettet, men aner ikke hva det heter. så...

Videoer, nettsider eller svar her blir tatt i mot med stor takk.

[Janhaa]

Dersom [tex]x[/tex] ikke var kvadrert ville den da hatt noen løsninger? Er det noen som vet hvordan slike oppgaver løses? Prøvde å søke litt på nettet, men aner ikke hva det heter. så...
Videoer, nettsider eller svar her blir tatt i mot med stor takk.

mener du sånn,

[tex]x\equiv 17 (\text mod \,71)[/tex]

[tex]x=17+k*71,\,\,\, k\in \mathbb{Z}[/tex]

generell løsning...

[Nebuchadnezzar]

ops tenkte mer på når vi har det enkle tilfellet bare med flere tall

[tex]x \equiv 2 \text{mod} (5)[/tex]
[tex]x \equiv 1 \text{mod} (6)[/tex]
[tex]x \equiv 1 \text{mod} (7)[/tex]

og et tilfelle hvor x ikke er alene

[tex]240x \equiv 8 \text{mod}(198)[/tex]

Føler jeg stiller så mange dumme spørsmål, men er bedre å stille dumme spørsmål nå enn på eksamen.

[Janhaa]

ops tenkte mer på når vi har det enkle tilfellet bare med flere tall
[tex]x \equiv 2 \text{mod} (5)[/tex]
[tex]x \equiv 1 \text{mod} (6)[/tex]
[tex]x \equiv 1 \text{mod} (7)[/tex]
og et tilfelle hvor x ikke er alene

denne løses med Chinese remainder theorem

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

[tex]240x \equiv 8 \text{mod}(198)[/tex]

skal vi sjå...

[tex]x = 240^{196} \cdot 8 +198*k,\,\,\, k\in \mathbb{Z}[/tex]

som generell løsning..

[Janhaa]

[tex]240x \equiv 8 \text{mod}(198)[/tex]
skal vi sjå...
[tex]x = 240^{196} \cdot 8 +198*k,\,\,\, k\in \mathbb{Z}[/tex]
som generell løsning..

Denne Nebu, fant jeg i ei bok.
plutarco og de som kan dette, får ta det formelle...

[Gustav]

Litt språklige ting:

Vi sier at et heltall n er en kvadratisk rest modulo et heltall p dersom det fins et heltall x slik at [tex]x^2\equiv n\,mod(p)[/tex]. Spørsmålet i den opprinnelige posten er altså om 17 er en kvadratisk rest modulo 71. Svaret er "nei" siden teoremet sier at antallet kvadratiske rester modulo primtallet 71 er [tex]1+17^{\frac{71-1}{2}}\, \equiv 1-1\equiv 0 \,mod(71)[/tex]. Her refererer jeg til wikipedia-artikkelen om kvadratiske rester(quadratic residues).

Har du et system av flere kongruenser bruker man, som Janhaa sier, det kinesiske restteoremet. Algoritmen er nøye beskrevet på wikipedia. Bevisene kan det være greit å ha gått gjennom ihvertfall én gang i løpet av tallteorikurset.

Ligningen [tex]240x\equiv 8\,mod(198)[/tex] har ingen heltallsløsning: Modulo 198 er [tex]240\equiv 42[/tex] så kongruensen kan skrives [tex]42x\equiv 8 [/tex]. Det betyr at 42x=8+198n. Men [tex]42x\equiv 0\,mod(3)[/tex] mens [tex]8+198n\equiv 2\,mod(3)[/tex], så ingen løsning fins.

kvadratisk rest == quadratic residue

kinesisk restteorem == chinese remainder theorem

[Nebuchadnezzar]

Prøver meg på den oppgaven med flere likninger jeg.

Leser litt om det kinesiske rest-teoremet og stopper litt opp. Prøver å løse oppgaven som et liknende eksempel. Men har problemer med å finne inversen eller noe slikt. JEg forstår ikke regningen under i eksempelet.

[tex]y_1 \equiv {(z_1)}^1 \text{mod} (m_1) \equiv (8400)^{-1} \text{mod} (11) \equiv (7)^{-1} \text{mod} (11) \equiv 8 \text{mod} (11)[/tex]

[Janhaa]

ops tenkte mer på når vi har det enkle tilfellet bare med flere tall
[tex]x \equiv 2 \text{mod} (5)[/tex]
[tex]x \equiv 1 \text{mod} (6)[/tex]
[tex]x \equiv 1 \text{mod} (7)[/tex]
.

[tex]x\equiv 2 \pmod{5}\\x\equiv 1 \pmod{6}\\x\equiv 1 \pmod{7}[/tex]

gir x=2+5k

[tex]2+5*k\equiv 1 \pmod{6}[/tex]
dvs
[tex]k\equiv 1 \pmod{6}[/tex]
gir

k=1+6*l
x=2+5*(1+6*l)=7+30*l
dvs
[tex]7+30*l\equiv 1 \pmod{7}[/tex]
[tex]30*l\equiv 1 \pmod{7}[/tex]
30*l=1+7*m
altså
x=7+(1+7m)=8+7m
dvs
[tex]x\equiv 8 \pmod{7}[/tex]

stemmer dettte...?
(oppskrift fra den geniale dao.)

[Nebuchadnezzar]

Jeg skrev opp en haug med tall, og sjekket en haug med rester. Selv kom jeg fram til

EDIT: Noe som bare var tull.

Forstår ikke helt overgangen fra

[tex]2+5k \equiv 1 (\text{mod})[/tex]

til

[tex]k \equiv 1 (\text{mod})[/tex]

Tester jeg ut et par verdier ser jeg jo at det logisk stemmer.

[Janhaa]

Jeg skrev opp en haug med tall, og sjekket en haug med rester. Selv kom jeg fram til
EDIT: Noe som bare var tull.
Forstår ikke helt overgangen fra
[tex]2+5k \equiv 1 (\text{mod6})[/tex]
til
[tex]k \equiv 1 (\text{mod6})[/tex]
Tester jeg ut et par verdier ser jeg jo at det logisk stemmer.

[tex]5k \equiv 1+6*1-2 (\text{mod6})[/tex]
[tex]5k \equiv 5 (\text{mod6})[/tex]
[tex]k \equiv 1 (\text{mod6})[/tex]

[Janhaa]

ops tenkte mer på når vi har det enkle tilfellet bare og et tilfelle hvor x ikke er alene
[tex]240x \equiv 8 \text{mod}(198)[/tex]
Føler jeg stiller så mange dumme spørsmål, men er bedre å stille dumme spørsmål nå enn på eksamen.

kan man her forenkle

[tex]30x \equiv 1 \pmod{198}[/tex]

plutarco?

[Nebuchadnezzar]

[tex]5k \equiv 1+6*1-2 (\text{mod6})[/tex]
[tex]5k \equiv 5 (\text{mod6})[/tex]
[tex]k \equiv 1 (\text{mod6})[/tex]

Skjønner ikke bæret her jeg. Blir frustrert over at jeg ikke forstår noenting av det over. Hoppet inn i faget tallteori litt seint, så prøver å jobbe litt hardt ei stund for å komme asur.

Bruker du at

[tex]2 + 5k \equi 1 (\text{mod6})[/tex]

Er det samme som

[tex]5k + 7 \equiv 1(\text{mod6})[/tex]

?

Og uten at jeg sier det for sikkert så tror jeg den omskrivningen din er lov. Står i boka her at man kan gange en kongrugens med et tall.Litt usikker på om det gjelder deling og. boka er god den, men altfor mye bevis, og litt lite konkrete oppgaver :p