# Show that $n = 3^{100} + 2$ is not a prime number.

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.

• $3^{100}+2$ has 8 divisors – Dr. Mathva Apr 14 at 15:25
• 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"... – Dr. Mathva Apr 14 at 15:28
• $3^{100}+2 \equiv 12^2 \mod 53$ so $\left( \frac{n}{53}\right) = 1$. – Robert Israel Apr 14 at 15:32
• Nice, @Robert Israel, but how do we know it is $12^2$? – Fareed AF Apr 14 at 15:38
• @FareedAF $53$ is not very big. You can enumerate $1^2 \mod 53$, $2^2 \mod 53$, ..., $26^2 \mod 53$. – Robert Israel Apr 14 at 15:52

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.

• 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). – Bill Dubuque Apr 14 at 19:49