sjekke om x^2 = 71 mod 17 er løsbar

[Nebuchadnezzar]

Skal vise at den kvadratiske kongurensen

[tex]x^2 \equiv 71\pmod{17}[/tex]

Ikke er løsbar.

---------------------

Her tenker jeg at det er litt vanskelig å regne ut

[tex]\left( 71 / 17 \right)[/tex]

Så derfor bruker jeg loven om kvadratisk resiprositet til å se at

[tex]\left( 71 / 17 \right)\left( 17 / 71 \right) = (-1)^{\left( \frac{17-1}{2}\right)\left( \frac{71-1}{2}\right) } = 1[/tex]

Siden både [tex]17[/tex] og [tex]71[/tex] er primtall.

som betyr at enten er begge de kvadratiske kongurensene løsbar, eller er ingen løsbare.

[tex]\left( 71 / 17 \right)=x[/tex]
[tex]\Updownarrow[/tex]
[tex]x \equiv 71^{\frac{17-1}{2}} \pmod{17}[/tex]
[tex]x \equiv 71^{8} \pmod{17}[/tex]
Litt usikker på hvordan jeg løser denne, litt for store tall for kalkulatoren min.
[tex]x \equiv 16 \equiv -1 \pmod{17}[/tex]

Altså er kongurensen
[tex]x^2 \equiv 71\pmod{17}[/tex] ikke løsbar.

Lurer mest på om det finnes noen bedre metode / hvordan en kan forenkle den siste likningen, da kalkisen kreperte.

[Vektormannen]

Husk på regnereglene for Legendresymbolet. Du har lov til å bytte ut 71 med et tall som er kongruent med 71 modulo 17...

[Nebuchadnezzar]

klarte den på min egen måte ^^

Skal prøve meg på din og =)

[tex]x \equiv 71^8 \pmod{17}[/tex]

[tex]x \equiv \left(71^2\right)^4 \pmod{17}[/tex]
som gir
[tex]x \equiv 71^2 \pmod{17}[/tex]
[tex]x \equiv 9 \pmod{17}[/tex]
altså

[tex]x \equiv \left(9\right)^4 \pmod{17}[/tex]
[tex]x \equiv 16 \pmod{17}[/tex]

Så med din metode blir det vel noe allà

[tex]x^2 \equiv 71 \pmod{17}[/tex]
[tex]x^2 \equiv 3 \pmod{17}[/tex]

[tex]L \equiv 3^{\frac{17-1}{2}} \pmod{17}[/tex]
[tex]L \equiv 16 \pmod{17}[/tex]
[tex]L \equiv -1 \pmod{17}[/tex]

Gav meg i det minste god trening i ulike metoder =)