Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$. – Michael Hardy Aug 2 '13 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 '13 at 22:13
The number is EVEN! – Ali Aug 3 '13 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. – Jeppe Stig Nielsen Aug 3 '13 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. – Ross Millikan Aug 3 '13 at 13:04
up vote 68 down vote accepted

$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.

share|cite|improve this answer
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. – nayrb Aug 2 '13 at 21:52

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

share|cite|improve this answer
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. – Jeel Shah Nov 5 '13 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... – DonAntonio Nov 5 '13 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. – Jeel Shah Nov 5 '13 at 14:03
I just love the precise nature of this answer. +1 – Asimov Sep 28 '14 at 18:31

$$ 83^{27} + 1 = \Big(83^9\Big)^3 + 1 = 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$.

share|cite|improve this answer

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!

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer
Would the downvoter care to comment? – robjohn Aug 3 '13 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 – Asimov Sep 28 '14 at 18:32

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$.

share|cite|improve this answer
Extebded answer to include this. – wendy.krieger Aug 3 '13 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....

share|cite|improve this answer

Let's ask WolframAlpha!

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")
share|cite|improve this answer

protected by Community Jun 21 '14 at 19:06

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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