# Prime Numbers (difficult question about something seemingly simple)

Show 40 post(s) from this thread on one page
Page 3 of 4 First 1234 Last
• Jun 6th 2010, 11:49 AM
yeah:)
Quote:

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?
• Jun 6th 2010, 12:03 PM
gmatt
Quote:

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.
• Jun 6th 2010, 12:25 PM
yeah:)
There must be an easier way! Has this forum given up?
• Jun 6th 2010, 01:57 PM
hmmmm
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
• Jun 6th 2010, 02:20 PM
gmatt
Quote:

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 $10^k+1$ must be of the form $10^{2^n}+1$ for some $n$.
• Jun 6th 2010, 02:42 PM
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?
• Jun 6th 2010, 02:46 PM
chiph588@
Quote:

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.
• Jun 6th 2010, 03:32 PM
yeah:)
So if the best mathematicians here are giving up, where do I go next?
• Jun 6th 2010, 03:41 PM
chiph588@
Quote:

Originally Posted by yeah:)
So if the best mathematicians here are giving up, where do I go next?

What's this problem for anyway?
• Jun 6th 2010, 04:12 PM
tonio
Quote:

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
• Jun 6th 2010, 04:27 PM
yeah:)
If there is no solution, how can I show that there is no solution?
• Jun 6th 2010, 04:47 PM
gmatt
Quote:

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 $10^{2^n}+1$ ) is not prime over a certain value of $n$ 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 $n=18$ Keller has compiled a list of known prime factors of the generalized fermat numbers, meaning they are all not prime.

Generalized Fermat Number -- from Wolfram MathWorld
and here
Fermat number - Wikipedia, the free encyclopedia .
• Jun 6th 2010, 05:13 PM
yeah:)
Would anyone care to set out such an answer?
• Jun 6th 2010, 05:19 PM
chiph588@
Quote:

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??
• Jun 6th 2010, 06:12 PM
undefined
Quote:

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.
Show 40 post(s) from this thread on one page
Page 3 of 4 First 1234 Last