# Quadratic Reciprocity: Determine if 11 is a quadratic residue $\mod p$for primes of the form: 44k+5?

I'm currently studying for exams and this has me stuck. A sample question from a past paper states:

Use the quadratic reciprocity theorem to determine whether $11$ is a quadratic residue $\mod p$ for primes of the form:

(i) $44k+5$

(ii)$44k+7$ etc...

Neither my books or my notes have any specific proofs related to this sort of mod p, so I would be very grateful if someone could go through the proof for the first value 44k+5. Step by step is vital.

My own progress

I do not know if its correct, but so far I have tried using what i think is the right formula: First, get ${1\over 2(p-1)} = 22k+2$ Second, list of numbers making up $44k+4$. This is the part confusing me. How the hell do I list numbers from 1 to $44k+4$ with $22k+2$ as the midway point? The book somewhat skips over this, assuming you just know how.

I have tried to make this question as clear as possible, but it is based on my own (very bad!) understanding of the question. Please feel free to ask for clarification if needed and I will supply it.

-

Assuming that $44k+5$ is prime and observing that it is $\equiv1\bmod4$, $$\left(\frac{11}{44k+5}\right)= \left(\frac{44k+5}{11}\right)=\left(\frac{5}{11}\right)=1$$ since $5\equiv4^2\bmod11$.

-
Hi Andrea. First off, thanks very much for the quick response. If you don't mind I would like to clarify some of the things you have done. I warn you, these questions are probably painfully obvious, but bear with me please. – David Ryan Dec 19 '12 at 17:49
To anticipate your questions: if $p$ and $q$ are odd primes, then $\left(\frac pq\right)\left(\frac qp\right)=\pm1$ and actually $=-1$ if and only if $p\equiv q\equiv3\bmod 4$. Also $\left(\frac pq\right)$ depends only on $p\bmod q$. – Andrea Mori Dec 19 '12 at 17:52
Thanks again. I also had some other questions if you don't mind. How did you evaluate 44k+5 congruent to 1 mod 4? Was it simply a case of adding 5 to 44, taking away the 1 and mod 4? Is this what allowed you to remove 44k from the following process? – David Ryan Dec 19 '12 at 17:59
Simply $44k+5=4(11k+1)+1$, and this takes care of the sign. But inside the symbol you have to reduce modulo $11$ (the "denominator") and clearly $44k+5=11(4k)+5$ so the "numerator" reduces to 5. – Andrea Mori Dec 19 '12 at 18:04
I believe I get the gist of what you are saying, but when I try applying it to 44k+7 I am falling flat on my face. So, 44K+7 is not congruent to 1 mod 4, so I check to see if it and 11 are congruent to 3 mod 4, which they are. This means I have -(p/q), so -(44k+7/11). Reducing Mod 11 this gives me -(7/11). I cannot find anything that is congruent to this, but I believe this calculation should work out that there is. Could you point out what I am doing wrong? Thanks again for your patience, and apologies for the lack of formatting. First time user of this site, and no idea how to format – David Ryan Dec 19 '12 at 18:41

Quadratic reciprocity states that if $p$ and $q$ are odd primes, then $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)(-1)^{(p-1)(q-1)/4}$.

Now, let $p=11$ and $q=44k+5$ (where this is a prime number). We have

$$\left(\frac{11}{44k+5}\right)=\left(\frac{44k+5}{11}\right)(-1)^{5(22k+2)}=\left(\frac{5}{11}\right)=\left(\frac{11}{5}\right)=\left(\frac{1}{5}\right)=1.$$

Therefore, $11$ is a square modulo a prime congruent to $5$ mod $44$.

It is worth going back and seeing why we needed it to be $44$ in the question. When we applied quadratic reciprocity, we had two simplifications that were made. The first was that $44k+5 \equiv 5 \pmod{11}$. This allowed us to simplify $\left(\frac{44k+5}{11}\right)$. For this to happen, we needed that $44$ is divisible by $11$. The second simplification needed was to simplify $(-1)^{\frac{11-1}{2}\frac{(44k+5)-1}{2}}=(-1)^{\frac{(44k+5)-1}{2}}$. For this term to not depend on the choice of $k$, we need $44k+5 \pmod 4$ not to depend on $k$. The reason this happens is because $44$ is divisible by $4$.

In summary, the reason they chose $44$ is because for the answer to not depend on the choice of $k$, they needed a coefficient which was a multiple of both $4$ and $11$. The least common multiple of $4$ and $11$ is $44$.

-
Thanks for your response Aaron. If you don't mind I would like to ask a question or two? – David Ryan Dec 19 '12 at 18:44
@DavidRyan Of course, ask away. – Aaron Dec 19 '12 at 19:47
@No worried, Andrea already answered them. Thanks again for the help and merry christmas. – David Ryan Dec 20 '12 at 14:01