Thread: Prime Numbers (difficult question about something seemingly simple)

Originally Posted by gmatt

Best bet at figuring this out is probably modifying Pepin's test and running an optimized computer program:

Pépin's test - Wikipedia, the free encyclopedia

That sounds rather complicated! Surely there must be a more simple way of proving this?

Originally Posted by yeah:)

That sounds rather complicated! Surely there must be a more simple way of proving this?

Fermat primes are very complicated, the primes you suggested are very similar to fermat primes.

There must be an easier way! Has this forum given up?

i suggested an answers a few post ago, not sure if it is right though but nobody responded thanks to that strange interupption, hope it helps sorry for this messed up thread

Originally Posted by hmmmm

ok so if we have that 10^m+1 is coposite for all odd m, then we assume m is even and so

10^m + 1 = 10^2k +1 = 100^k + 1 and so if k is odd then we have the number is composite, if it is not then we just repeat the process until we have the exponent as an odd number which we will get as m must be a finite, and so there are no more primes of this form, is this helpful??

This was first stated by Roninpro in the first response, that is the only possible primes of the form must be of the form for some .

sorry if i am being stupid here but why does this mean that 10^(2^n) + 1 are excluded, surely they can be reduced using this same process?

Originally Posted by hmmmm

sorry if i am being stupid here but why does this mean that 10^(2^n) + 1 are excluded, surely they can be reduced using this same process?

Because the method I used shows that a divisor of 10^2^n+1 is 10^2^n+1. This doesn't show it's composite.

On a side note, I think it's time for this tread to die.

So if the best mathematicians here are giving up, where do I go next?

Originally Posted by yeah:)

So if the best mathematicians here are giving up, where do I go next?

What's this problem for anyway?

Originally Posted by yeah:)

So if the best mathematicians here are giving up, where do I go next?

Ask your instructor: either0she/he has a solution nobody has thought about here, or else she/he'll tell you there's no known answer. Instructors sometimes do that.

Tonio

If there is no solution, how can I show that there is no solution?

Originally Posted by yeah:)

If there is no solution, how can I show that there is no solution?

You assume there exists a solution and show that it would imply a contradiction.

What you are asking is basically for a method to prove that a generalized fermat number (in this case ) is not prime over a certain value of which is an open problem in mathematics as far as I know.

If this homework is from a computer-science class maybe your prof wants you to devise a method to test for primality, in which case Pepin's test would probably be the best approach (for deterministic primality, for probabilistic primality other algorithms may work better.)

Please refer to GFN10 factoring status if you don't believe me that this is an open problem. So far, up to Keller has compiled a list of known prime factors of the generalized fermat numbers, meaning they are all not prime.

You can read more about fermat numbers here
Generalized Fermat Number -- from Wolfram MathWorld
and here
Fermat number - Wikipedia, the free encyclopedia .

Would anyone care to set out such an answer?

Originally Posted by yeah:)

Would anyone care to set out such an answer?

Clearly we don't know how to get any further. We're not here to do your work for you anyway. What have you tried??

Originally Posted by yeah:)

Would anyone care to set out such an answer?

As gmatt said, this is an open problem in mathematics. Asking us to solve it for you is like asking us to prove or disprove the Goldbach conjecture or the Riemann hypothesis for you.

It may interest you to know that this exact question has been asked before on another thread in another forum (which I found through a Google search). Over there, someone came up with the spin of interpreting the numbers as given in base 2, for which the question can be easily answered. Except for that spin, the same conclusion was reached over there as over here.