# Is $83^{27} +1$ a prime number?

I'm having problems with exercises on proving whether or not a given number is prime. Is $83^{27} + 1$ prime?

• Someone else points out that it can't be prime because it's even. That's probably the quickest way. May answer shows how to factor it (so it can't be prime) by a method that would work just as well if it had been $84^{27}+1$. Aug 2, 2013 at 22:11
• Wolfram Alpha says that $83^{27}+1= 2^2×3^4×7×109×757×2269×9613×49339×2208799×14685985270709080390792801$. Perhaps it's fun to try to prove that 3 and 7 are factors.
– lhf
Aug 2, 2013 at 22:13
• The number is EVEN!
– Ali
Aug 3, 2013 at 5:37
• @Joseph It is "well-known" and not too hard to prove that if $b^n+1$ is prime for some integer $b>1$ then $n$ has to be zero or a power of two. And 27 is neither zero nor a power of two. Search for Generalized Fermat Prime to find a proof, or do the proof yourself. Aug 3, 2013 at 6:48
• If it is for a test, the simple answer is that you don't have the tools to prove it prime, so it must be composite. Aug 3, 2013 at 13:04

$83$ is odd, so is any power of $83$. Hence $83^{27}+1$ is even, but the only even prime number is $2$ and this number is not $2$.

More generally, if $a,k\in\mathbb N$ and $k$ is odd, then $$a^k+1\equiv (-1)^k+1\equiv 0\pmod{a+1}$$ So $a+1\mid a^k+1$. In this case this yields $84=2^2\cdot 3\cdot 7$ as divisor.

• Your last statement can also be seen by geometric series: $(1+x+\cdots+x^{k-1})(x-1)=x^k-1$. For $k$ odd, substitute $x=-a$ and cancel out the minuses signs on each side to get the factor $(a+1)$ on the left with $a^k+1$ on the right. Aug 2, 2013 at 21:52

Well, it is an even number, so...

• I downvoted your answer on the basis that it doesn't provide the reason behind why it is even. For example, it doesn't say that since $83$ is odd, so the powers of it must also be odd and thus, odd + 1 must be even. Nov 5, 2013 at 3:37
• @gekkostate: (1) If you think all the answers must provide all the reasons behind them then you're going to downvote a lot around here, as many participants, probably most of the serious ones, don't think like you do. (2) The question is at a level that requires as trivial to know that powers of odd numbers are odd, and sum of odd numbers is even, so to add that to the answer seems trivial after it's been remarked that the number is odd (and thus the OP begins to think "why?" and he completes the answer by himself). Think of this, perhaps you'll realize you rush too much to do downvote... Nov 5, 2013 at 4:51
• I clearly failed to see the intent behind your answer but I still feel that it lacks any reasoning whatsoever. Your answer is equivalent to the highest upvoted comment so maybe, that should have been enough? Also, I hardly ever downvote questions/answers (ratio of up to down is 77/5) so I didn't really rush into this (clearly, I use downvotes sparingly). I don't want to make this into something that it is not. Let's leave this at the fact that we have a difference of opinions on answers. Nov 5, 2013 at 14:03
• I just love the precise nature of this answer. +1 Sep 28, 2014 at 18:31

$$83^{27} + 1 = \Big(83^9\Big)^3 + 1^3 = a^3+b^3 = (a+b)(a^2-ab+b^2) = \Big(83^9+1\Big)\Big((83^9)^2-83^9+1\Big).$$

So, no, it's not prime.

PS (added later): Some point out that it's obviously an even number, so it's not prime. But what I do above would work just as well if it were $$84$$ rather than $$83$$.

Note that $83\equiv -1\pmod{84}$. Thus $83^{27}+1\equiv 0\pmod{84}$.

It follows that our number is divisible by all the divisors of $84$.

It is also non-prime in other ways. For let $x=83^3$. Then our number is $x^9+1$, so is divisible by $x+1$. Similarly, we could let $y=83^9$, and conclude that our number is divisible by $y+1$.

Seriously non-prime!

We have a chain of divisibilities, based on the fact that $(a-b)\mid(a^n-b^n)$, $$83^1-(-1)^1\mid83^3-(-1)^3\mid83^9-(-1)^9\mid83^{27}-(-1)^{27}=83^{27}+1$$ Using this chain, we get, using $a^3-b^3=(a-b)(a^2+ab+b^2)$, \begin{align} 83^{27}+1 &=\frac{83^{27}+1}{83^9+1}\times\frac{83^9+1}{83^3+1}\times\frac{83^3+1}{83^1+1}\times\left(83^1+1\right)\\ &=\left(83^{18}-83^9+1\right)\times\left(83^6-83^3+1\right)\times\left(83^2-83^1+1\right)\times\left(83^1+1\right)\\[9pt] &=34946659039493167203883141969862007\times326939801583\times6807\times84 \end{align} Thus, $83^{27}+1$ is not prime.

Note: none of these factors are guaranteed to be prime, just factors.

• Would the downvoter care to comment?
– robjohn
Aug 3, 2013 at 19:37
• I like it. Some might say overly rigorous for a simple problem, but helps demonstrate some deeper thinking than just noticing that it would be even. +1 Sep 28, 2014 at 18:32

It is obviously not prime. $83$ is odd, therefore $83^{27}$ is odd, hence $83^{27}+1$ is even and not prime.

The only prime numbers of the form $a^x+b^x$, occur when $x$ is a power of two. This does not guarantee a prime, but if $x$ is not a power of $2$, then the number has algebraic factors.

In practice, there is an algebraic divisor of $a^n-b^n$, for each $m$ that divides $n$. For the equation $a^n+b^n$, one would look for divisors of $2n$ that don't divide $n$. Inthe question we have $n=27$, so the divisors of 54 that don't divide 27. That is, 2, 6, 18 and 54. For powers of 2, there is only one number that divides $2n$ but not $n$.

• Extebded answer to include this. Aug 3, 2013 at 23:44

well it is divisible by $84$ and in general $\forall a,m\in\mathbb {N}$ we have $(a+1)\mid (a^{2m+1}+1)$ So....

PrimeQ[83^27 + 1]

is $$6\,532\,937\,361\,590\,551\,025\,727\,805\,459\,013\,652\,074\,798\,022\,177\,030\,828$$ a prime number?

$$83^{27} + 1$$ is not a prime number

$$2^2 \times 3^4 \times 7 \times 109 \times 757 \times 2269 \times 9613 \times 49339 \times 2208799 \times 14685985270709080390792801 \space\text{(14 prime factors, 10 distinct)}$$

However, using basic knowledge that an odd times an odd is always an odd ($$3 \times 3 = 9$$), we see that $$83$$ (an odd number) raised to any power is an odd number. Then we add one to it and get an even number.

Being even (and obviously not equal to $$2$$), the definition of a prime tells us that the number is not prime because it is divisible by $$2$$ (my words):

prime (noun):

1. Any natural number, greater than $$1$$, that, when divided by any natural number, greater than $$1$$, other than itself or $$1$$ does not result in a natural number.
2. Any "natural number greater than $$1$$ that has no positive divisors other than $$1$$ and itself." (Wikipedia article "prime number")