3
$\begingroup$

So I have to prove that $n = 3^{100} + 2$ is not a prime number while we assume that $X^2 - 53$ has no zeroes in $\mathbb{Z}/n\mathbb{Z}$.

Because we are working with quadratic reciprocity in this chapter, I assumed that $\big(\frac{53}{n}\big) = -1$ and by the law of quadratic reciprocity, we know that $\big(\frac{n}{53}\big) = -1$. However, I have no clue how I could use this to prove that $n$ is not prime.

$\endgroup$
  • 1
    $\begingroup$ $3^{100}+2$ has 8 divisors $\endgroup$ – Dr. Mathva Apr 14 at 15:25
  • $\begingroup$ You've written at the beginning "So I have to prove that $n=3^{100}+2$ is a prime number". Nevertheless, in the end, you claim that you want "to prove that $n$ is not prime"... $\endgroup$ – Dr. Mathva Apr 14 at 15:28
  • 2
    $\begingroup$ $3^{100}+2 \equiv 12^2 \mod 53$ so $\left( \frac{n}{53}\right) = 1$. $\endgroup$ – Robert Israel Apr 14 at 15:32
  • $\begingroup$ Nice, @Robert Israel, but how do we know it is $12^2$? $\endgroup$ – Fareed AF Apr 14 at 15:38
  • 1
    $\begingroup$ @FareedAF $53$ is not very big. You can enumerate $1^2 \mod 53$, $2^2 \mod 53$, ..., $26^2 \mod 53$. $\endgroup$ – Robert Israel Apr 14 at 15:52
4
$\begingroup$

If you're looking for a proof that the true $(3^{100}+2|53)=+1$, here is my approach:

Multiply be $3^4$, a known square, so:

$(3^{100}+2|53)=(3^{104}+3|53)$

where $2×3^4=162\equiv 3\bmod 53$. The exponent on $3$ in the large term is now a multiple of $52$ forcing $3^{104}\equiv 1$ By Fermat's Little Theorem. Thereby

$(3^{100}+2|53)=(1+3|53)=(2^2|53)=+1$

but you found that a prime number for $(3^{100}+2)$ should have given the Legendre symbol $-1$. As an old hit song says, this is how it is when doves cry.


Even though the above Legendre symbol is $+1$, what causes $X^2-53=0$ to have no solutions in $\mathbb{Z}/n\mathbb{Z}$ is a prime factor $p$ of $n=3^{100}+2$ for which $(53|p)=-1$. The above proof does not identify any such factors, but the factor $37121$ quoted by others has this property.

$\endgroup$
  • 1
    $\begingroup$ Right. Had the OP replied to my comment I was going to note $\large \!\bmod 53\!:\,3^{\large 4} n\equiv 2^{\large 2}\,$ so $\,\large\,n\equiv (2/9)^{\large 2},\,$ essentially the same as above (but doesn't require any knowledge of Legendre symbols). $\endgroup$ – Bill Dubuque Apr 14 at 19:49

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.