Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having problems with this type of exercises, proving whether or not a given number is prime.

share|improve this question
3  
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
5  
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
39  
The number is EVEN! –  Ali Aug 3 '13 at 5:37
3  
@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
3  
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
show 9 more comments

9 Answers

up vote 56 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|improve this answer
3  
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
add comment

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

share|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. –  gekkostate Nov 5 '13 at 3:37
2  
@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. –  gekkostate Nov 5 '13 at 14:03
add comment

$$ 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|improve this answer
add comment

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|improve this answer
add comment

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

share|improve this answer
add comment

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|improve this answer
2  
Would the downvoter care to comment? –  robjohn Aug 3 '13 at 19:37
add comment

Taking the cheater's way out with Wolfram|Alpha:

is ((83^27)+1) prime?

 

is $6532937361590551025727805459013652074798022177030828$ a prime number?

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

$2^2×3^4×7×109×757×2269×9613×49339×2208799×14685985270709080390792801$


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. Then we add one to it, and common knowledge tells us that the number is now even.

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 whole number, greater than 1, other than itself or one does not result in a whole number.
  2. Any "natural number greater than 1 that has no positive divisors other than 1 and itself." (Wikipedia article "prime number")
share|improve this answer
add comment

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|improve this answer
    
Extebded answer to include this. –  wendy.krieger Aug 3 '13 at 23:44
add comment

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|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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