I'm working through an exam paper and this is the final part to a question regarding Legendre Symbols. I've attempted each part, but I'm having problems with parts i) and iii) in particular which are probably the easiest parts of the question. Guidance on how to answer parts i) and iii) and feedback on my solutions to the other parts would be appreciated.

Let p be prime and suppose that

$$p=2^{2^n}+1$$ for some $n \geq{2}$.

i) Show that $p \equiv{2}\mod5$

So far I have deduced that I need to use $2^{2^n}=4^{2^n-1} \equiv{(-1)^{2^{n-1}}}\mod 5$.

ii) Use Gauss' Law of Quadratic Reciprocity to obtain,


Firstly, $(\frac{5}{p})=(\frac{p}{5})$ by quadratic reciprocity since $5 \equiv{1}\mod4$. Then $1^2 \equiv{1}\mod5, 2^2 \equiv{4}\mod5, 3^2 \equiv{4}\mod5, 4^2 \equiv{1}\mod5$. So we can conclude that $(\frac{5}{p})=-1$ if $p \equiv{2}\mod5$. (I have ignored the case $p \equiv{3}\mod5$ as the question doesn't require evidence of this solution.)

iii) Use Euler's Criterion to deduce that $5^{2^{2^{n}-1}} \equiv{-1}\mod p$.

Euler' criterion states that $(\frac{a}{p}) \equiv{a^{\frac{p-1}{2}}}\mod\text{p}$. So $(\frac{5}{p})\equiv{5^\frac{2^{2^{n}}+1-1}{2}}\mod p \equiv{5}^\frac{4^{2^{n}-1}}{2}\mod p $.

(I keep making a mess of this question so any advice would be appreciated).

iv) Show that the order of 5 modulo p is equal to $2^m$ for some $m\leq{2^n}$.

I think that by squaring both sides we obtain $5^{2^{2^{n}}}=1$ which tells us that the order is $2^m$ for some $m\le{2^n}$.

v) Deduce that 5 is a primitive root modulo p.

I know I need to prove that $m=2^n$. By Fermat's Little Theorem $a^{p-1} \equiv{1}\mod p$ which implies that $a^{2^{m}} \equiv{1}\mod p$. Now, a must have an order $2^i$ for some $0\leq{i}\leq{m}$ by Lagrange's Theorem. Since,

$$(\frac{5}{p})=-1$$ and by Euler's criterion $5^{2^{2^{n}-1}} \equiv{-1}\mod p$ we know that 5 cannot have order $2^i$ for some $0\leq{i}<{m}$. So $5$ has order $2^m$ and thus is a primitive root.


Some hints:

On 1, use $(-1)^{2k}\equiv 1\bmod 5$.

On 3, I'm pretty sure there's a typo in the question (or at least how it's typed here; with all the superscripts it's not that hard to misread it). It's true that

$$5^{2^{2^n-1}} \equiv -1 \bmod p$$

but not that

$$5^{2^{2^{n-1}}} \equiv -1 \bmod p.$$

(Also, with this typo your reasoning is slightly incorrect in 4), but with $2^{2^n-1}$ it becomes correct.)

Edit: On 3, You have

$$-1\equiv 5^{\frac{2^{2^n}}{2}}$$

which is pretty much exactly what you want (just written differently).

  • $\begingroup$ Thank you for the advice. I've also fixed the typos. $\endgroup$ – MichealAlex456 Jul 16 '17 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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