http://farm5.static.flickr.com/4068/...a8246422_b.jpg

Any ideas?

- Jun 5th 2010, 02:44 AMyeah:)Prime Numbers (difficult question about something seemingly simple)
- Jun 5th 2010, 06:51 AMroninpro
It might help to note that the numbers you are considering have the form . Can you see how to use that to factor 1001?

I tried to search for additional primes in this sequence and could not find any. (I believe that if a number of the form is prime, then must be of the form . I'm a bit too lazy to prove it right now.) Can part (b) even be fulfilled? - Jun 5th 2010, 08:57 AMyeah:)
So can anyone do part b)?

- Jun 5th 2010, 09:28 AMchiph588@
Haven't put too much thought into part b, but what I can tell you is a number of that form with an even number of zero's will always be divisible by .

Divisibility rule - Wikipedia, the free encyclopedia - Jun 5th 2010, 09:33 AMundefined
For what it's worth, I've used PARI/GP to test numbers of the form 10^n+1 from n = 3 up to n = 6000 without finding any primes. To my knowledge, PARI's isprime() is deterministic rather than probabilistic.

- Jun 5th 2010, 10:05 AMyeah:)
What about 100501???

- Jun 5th 2010, 10:09 AMundefined
- Jun 5th 2010, 03:41 PMchiph588@
We're looking at . Suppose where is odd.

. Thus we see is composite for all such that .

So the only remaining case to show are numbers of the form . I'll see what I can come up with. - Jun 5th 2010, 03:58 PMtonio
- Jun 5th 2010, 04:02 PMchiph588@
- Jun 5th 2010, 05:12 PMyeah:)
So, is there any definitive way of solving/proving part b)?

- Jun 5th 2010, 05:15 PMchiph588@
- Jun 5th 2010, 05:21 PMyeah:)
I can see that...if you have any more ideas, please post them up! I would really like to know how to solve this question!

- Jun 5th 2010, 08:48 PMBacterius
Ok, so the question is : for which is prime.

**Theorem**: if , then if is odd.

The proof is trivial, if . This only works for odd due to the special status of square roots in a congruence ring.

Now, let and (since is prime). Then divides all numbers of the form where is odd. That is, 50% of all concerned numbers.

Then, let and (since is prime). Then 101 divides all numbers of the form where is odd (2, 6, 10, ...).

So we're still missing the numbers of the form with even. Let's look at . This one's got to be composite (divisible by ) since the exponent is odd.

This is as far as I can go yet. I'm missing numbers of the form for even :( - Jun 5th 2010, 08:52 PMBacterius
Perhaps actually setting with even, then :

Then breaking the congruence :

and

And working with both : we've got some kind of Mersenne number on one side, and the other one's got to be composite (divisible by 2). These are just ideas, I don't even know if it's valid to break up a congruence in such a way.