# Prime or composite

1. Sep 5, 2010

### sachinism

is (2^{58}+1)/5 a prime number or a composite number

trust me this one has got an interesting solution

2. Sep 5, 2010

### phyzguy

Well, it appears that it is 107367629 * 536903681. Why is this of interest?

3. Sep 5, 2010

### law&theorem

If the result is fraction, it will make nonsense to discuss this question.
So, the result must be integral number.
Then, if (2^{58}+1) can be divided exactly by 5, the units of (2^{58}+1) must be 0 or 5. Science 2^{58} is even number, (2^{58}+1) must be odd number.
So, the units of (2^{58}+1) must be 5.
Then assume (2^{58}+1)=x+5, the units of x must be 0.
And units of x/5 must be 2, namely x can be divided exactly by 5.
So, (x+5)/5 can be divided exactly by 3.
So ,the question solved, the (2^{58}+1)/5 is a composite number.

Last edited: Sep 5, 2010
4. Sep 5, 2010

### law&theorem

And this question can be solved in this way:
(2^{58}+1)=(4^{29}+1)=([5-1]^{29}+1)=C(29,0)*5^29*(-1)^0+C(29,1)*5^28*(-1)^1+C(29,2)*5^27*(-1)^2+……+C(29,29)*5^0*(-1)^29+1;
C(29,29)*5^0*(-1)^29=-1, so C(29,29)*5^0*(-1)^29+1=0.
And the other items can all be divided exactly by 5, and (2^{58}+1)/5 is a composite number.

5. Sep 5, 2010

### Gokul43201

Staff Emeritus
Okay, so far.
You lost me at that step. Also, are you saying (2^{58}+1)/5 is divisible by 3?

Okay so far.
And again, I don't see how you arrived at that. What you have proved is that (2^{58}+1) is composite (specifically that it is divisible by 5).

6. Sep 5, 2010

### law&theorem

That means x+5 can be divide exactly by 15, so (x+5)/5 can be divided exactly by 3.

the second derivation is something wrong, I'll get another method

7. Sep 6, 2010

### phyzguy

Not sure what you guys are arguing about. As I said in post #2, (2^{58}+1)/5 has only two prime factors, 107367629 and 536903681, so it is demonstrably not divisible by 3.

8. Sep 6, 2010

### Gokul43201

Staff Emeritus
How do you arrive at that?

See phyzguy's post. It is not divisible by 3.

9. Sep 6, 2010

### hamster143

Here's the solution (I actually engineered it backwards, knowing the prime factors):

$$2^{58}+1 = 2^{58} + 2*2^{29} + 1 - 2^{30} = (2^{29}+1)^2 - 2^{30} = (2^{29}-2^{15}+1)(2^{29}+2^{15}+1)$$

More generally, it follows that all $2^{4n+2}+1$ are composite.

At the same time, as law&theorem showed, $5|2^{58}+1$, which is a special case of the fact that $5|2^{2(2n+1)}+1$, which, in turn, is a special case of the fact that $a^k+1|a^{k(2n+1)}+1$.

So we can conclude that all $(2^{4n+2}+1)/5$ are composite.

Last edited: Sep 6, 2010
10. Sep 6, 2010

### ramsey2879

Not true for n = 1

11. Sep 6, 2010

### hamster143

Agreed. $(2^{4n+2}+1)/5$ is composite as long as $2^{2n+1}-2^{n+1}+1>5$, which is true for $n\geq 2$.