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 $\displaystyle 10^n+1$. 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 $\displaystyle 10^n+1$ is prime, then $\displaystyle n$ must be of the form $\displaystyle 2^k$. 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 $\displaystyle 11 $.

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 $\displaystyle 10^a+1$. Suppose $\displaystyle a=2^ns $ where $\displaystyle s $ is odd.

$\displaystyle 10^a+1=\left(10^{2^n}\right)^s+1\equiv(-1)^s+1=0\bmod{(10^{2^n}+1)} $. Thus we see $\displaystyle 10^a+1 $ is composite for all $\displaystyle a $ such that $\displaystyle s\neq1 $.

So the only remaining case to show are numbers of the form $\displaystyle 10^{2^n}+1, \; n>3 $. I'll see what I can come up with. - Jun 5th 2010, 03:58 PMtonio

I don't get it:

(1) Did you mean $\displaystyle \left(10^{2^n}\right)^s+1\equiv(-1)^s+1\!\!\!\pmod{10^{2^n}}$ ? This is absurd, and then looking at the extremes you get:

2) $\displaystyle 10^a+1=0\!\!\!\pmod{10^{2^n}}$ , which is also absurd...or, perhaps very probably, I misunderstood something.

Tonio - 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 $\displaystyle k$ is $\displaystyle 10^k + 1$ prime.

**Theorem**: if $\displaystyle p | 10^k + 1$, then $\displaystyle p | 10^{mk} + 1$ if $\displaystyle m$ is odd.

The proof is trivial, if $\displaystyle 10^k \equiv -1 \pmod{p} \ \implies \ 10^{mk} \equiv {(-1)}^m \pmod{p} \ \implies \ 10^{mk} + 1 \equiv 0 \pmod{p}$. This only works for odd $\displaystyle m$ due to the special status of square roots in a congruence ring.

Now, let $\displaystyle k = 1$ and $\displaystyle p = 10^1 + 1 = 11$ (since $\displaystyle 11$ is prime). Then $\displaystyle 11$ divides all numbers of the form $\displaystyle 10^m + 1$ where $\displaystyle m$ is odd. That is, 50% of all concerned numbers.

Then, let $\displaystyle k = 2$ and $\displaystyle p = 10^2 + 1 = 101$ (since $\displaystyle 101$ is prime). Then 101 divides all numbers of the form $\displaystyle 10^{2m}$ where $\displaystyle m$ is odd (2, 6, 10, ...).

So we're still missing the numbers of the form $\displaystyle 10^{2m} + 1$ with $\displaystyle m$ even. Let's look at $\displaystyle 10^{2m - 1} + 1$. This one's got to be composite (divisible by $\displaystyle 11$) since the exponent is odd.

This is as far as I can go yet. I'm missing numbers of the form $\displaystyle 10^{2m} + 1$ for $\displaystyle m$ even :( - Jun 5th 2010, 08:52 PMBacterius
Perhaps actually setting $\displaystyle 10^{2m} + 1$ with $\displaystyle m$ even, then :

$\displaystyle 10^{2m} \equiv -1 \pmod{p}$

$\displaystyle 2^{2m} \times 5^{2m} \equiv -1 \pmod{p}$

Then breaking the congruence :

$\displaystyle 2^{2m} \equiv \pm 1 \pmod{p}$ and $\displaystyle 5^{2m} \equiv \mp 1 \pmod{p}$

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.