enter image description here

I know that $p_i$ is an odd prime, $(\frac{a}{p_i}\equiv a^{\frac{p_i-1}{2}} \pmod p$).

But I don't know how to solve this problem...


First note that for $(a,n)=1$, $a^{n-1}\equiv 1 \pmod{n}$, so $n$ must be a product of distinct odd primes, or we would have $p\mid \phi(n)$, so there would be $a$ with $(a,n)=1$, and $a$ has order $p$ in the multiplicative group. But then we'd have $p\nmid n-1$, so we can't have $a^{n-1}\equiv 1\pmod{n}$.

Then by the Chinese remainder theorem, we have that $$\newcommand{\ZZ}{\mathbb{Z}}\ZZ/n\ZZ\cong \prod_i \ZZ/p_i\ZZ$$ for $p_i$ distinct odd primes. Then looking coordinatewise, we see that for each prime $p_i$, $a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)\pmod{p_i}$. Assume for contradiction that $n$ is not itself prime, so that $n/p_i\ne 1$. Then multiplying each side of our equation by $\left(\frac{a}{p_i}\right)$, we have $$a^{(p_i(n/p_i)+p_i)/2-1}=a^{p_i(n/p_i+1)/2 - 1}=a^{-1}(a^{p_i})^{(n/p_i+1)/2}=a^{(n/p_i-1)/2}=\left(\frac{a}{n/p_i}\right)\pmod{p_i}.$$

Now in particular, this is true for $i=1$. I.e., we have that $$a^{(n/p_1-1)/2}=\left(\frac{a}{n/p_1}\right)\pmod{p_1}.$$ However, applying the Chinese remainder theorem, we can choose $a$ to be 1 mod $p_i$ for $i\ne 2$, and $a$ to be a nonsquare mod $p_2$. Then this equation becomes $$1=-1 \pmod{p_1}.$$

Contradiction. Hence $n$ must be prime.


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.