Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

1.) Compute the squares modulo 23 as efficiently as possible.

2.) Show that $y^2 = 23x^2 + 7$ has no integer solutions.

This is a two part problem on my review for number theory and I am a bit lost. After going to my professor with this his hint was for part 2 saying to reduce it to mod 23. Having a really tough time with this problem any help is greatly appreciated.

share|cite|improve this question
    
What does "efficiently" mean? For example, you only need to check all the integers modulo $\;23\;$ between $\;0\;$ and $\;11\;$ ... – Joanpemo Mar 12 at 22:04
    
Well, if you know quadratic reciprocity then it's quite fast. But even without that, brute force is quite efficient. – lulu Mar 12 at 22:04

The squares modulo $\;23\;$ are $\;0,1,4,9,16,2,13,3,18,12,8,6\;$ , so

$$y^2=23x^2+7=7\pmod{23}$$

and there's no element that squared modulo $\;23\;$ equals $\;7\pmod{23}\;$ .

share|cite|improve this answer
    
Appreciate it, how did you calculate the squares of mod 23? – Nick Powers Mar 12 at 22:15
1  
@NickPowers As I wrote in my comment: square by hand the elements $\;\mod{23}\;$ between $\;0\;$ and $\;11\;$ . Can you see why this is enough? – Joanpemo Mar 12 at 22:18
    
Shouldn't 8 squared be 18 not 19? – Nick Powers Mar 12 at 22:25
1  
Just to confirm what I did was right. And yes I see why we only go u to 11, because after that it repeats the same numbers in reverse order. – Nick Powers Mar 12 at 22:25
    
@NickPowers Thank you, yes: a typo. Corrected. And yes, that's the reason as raising to an even power a number or its negative is the same. – Joanpemo Mar 12 at 22:30

Answering part 2 only. We immediately see that $-7\equiv16\pmod{23}$ is a quadratic residue, because it is a square. Because $23\equiv-1\pmod4$ we also know that $-1$ is not a QR mod $23$. As the Legendre symbol is a multiplicative character this means that $7$ is a quadratic non-residue.


An afterthought about part 1. We immediately see that $2\equiv5^2$ is quadratic residue. So are its powers $1,2,4,8,16,32\equiv9, 18, 36\equiv13,26\equiv3,6,12$. That's eleven residue classes, so we are done. Of course, the fact that $(11,23)$ is a Sophie Germain pair of primes makes finding a generator for the group of QRs easy.

share|cite|improve this answer
1  
When $-1$ (and $2$) are QRs or QNRs comes up so often that it is second nature to look at those first. – Jyrki Lahtonen Mar 12 at 22:37

METHOD $1$

Use that $5$ is a primitive root

$$7 \not \in \mathbb{U}=\left\{5^2, 5^4, 5^6, \dots, 5^{22} \right\} \equiv \left\{2, 2^2, 2^3, \dots, 2^{11} \right\}=\left\{2,4,8,16,9,18,13,3,6, 12, 1\right\}$$

METHOD $2$

$$(\frac{7}{23})=-(\frac{23}{7})=-(\frac{16}{7})=-1$$ by quadratic reciprocity.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.