Is (2^58+1)/5 a Prime or Composite Number?

[sachinism]

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

trust me this one has got an interesting solution

 

[phyzguy]

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

 

[law&theorem]

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

trust me this one has got an interesting solution

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.

 

[law&theorem]

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

trust me this one has got an interesting solution

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.

 

[Gokul43201]

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.

Okay, so far.

So, (x+1)/5 can be divided exactly by 3.
So ,the question solved, the (2^{58}+1)/5 is a composite number.

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

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,

Okay so far.

...and (2^{58}+1)/5 is a composite number.

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

 

[law&theorem]

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

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

 

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

 

[Gokul43201]

That means x+5 can be divide exactly by 15,

How do you arrive at that?

... so (x+5)/5 can be divided exactly by 3.

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

 

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

 

[ramsey2879]

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.

Not true for n = 1

 

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