Prime Numbers (difficult question about something seemingly simple)

**yeah:)** · June 5th 2010, 02:44 AM

Any ideas?

**roninpro** · June 5th 2010, 06:51 AM

It might help to note that the numbers you are considering have the form $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 $10^n+1$ is prime, then $n$ must be of the form $2^k$ . I'm a bit too lazy to prove it right now.) Can part (b) even be fulfilled?

**yeah:)** · June 5th 2010, 08:57 AM

So can anyone do part b)?

**chiph588@** · June 5th 2010, 09:28 AM

Originally Posted by yeah:)

So can anyone do part b)?

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

Divisibility rule - Wikipedia, the free encyclopedia

**undefined** · June 5th 2010, 09:33 AM

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.

**yeah:)** · June 5th 2010, 10:05 AM

What about 100501???

**undefined** · June 5th 2010, 10:09 AM

Originally Posted by yeah:)

What about 100501???

You mean 10^100501 + 1? That returns composite.

**chiph588@** · June 5th 2010, 03:41 PM

We're looking at $10^a+1$ . Suppose $a=2^ns$ where $s$ is odd.

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

So the only remaining case to show are numbers of the form $10^{2^n}+1, \; n>3$ . I'll see what I can come up with.

**tonio** · June 5th 2010, 03:58 PM

Originally Posted by chiph588@

We're looking at $10^a+1$ . Suppose $a=2^ns$ where $s$ is odd.

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

So the only remaining case to show are numbers of the form $10^{2^n}+1, \; n>3$ . I'll see what I can come up with.

I don't get it:

(1) Did you mean $\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) $10^a+1=0\!\!\!\pmod{10^{2^n}}$ , which is also absurd...or, perhaps very probably, I misunderstood something.

Tonio

**chiph588@** · June 5th 2010, 04:02 PM

Originally Posted by tonio

I don't get it:

(1) Did you mean $\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) $10^a+1=0\!\!\!\pmod{10^{2^n}}$ , which is also absurd...or, perhaps very probably, I misunderstood something.

Tonio

Whoops! I had a typo. Take a look at my post again.

**yeah:)** · June 5th 2010, 05:12 PM

So, is there any definitive way of solving/proving part b)?

**chiph588@** · June 5th 2010, 05:15 PM

Originally Posted by yeah:)

So, is there any definitive way of solving/proving part b)?

Well, read my posts. It's being narrowed down.

**yeah:)** · June 5th 2010, 05:21 PM

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!

**Bacterius** · June 5th 2010, 08:48 PM

Ok, so the question is : for which $k$ is $10^k + 1$ prime.

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

The proof is trivial, if $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 $m$ due to the special status of square roots in a congruence ring.

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

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

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

This is as far as I can go yet. I'm missing numbers of the form $10^{2m} + 1$ for $m$ even

**Bacterius** · June 5th 2010, 08:52 PM

Perhaps actually setting $10^{2m} + 1$ with $m$ even, then :

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

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

Then breaking the congruence :

$2^{2m} \equiv \pm 1 \pmod{p}$ and $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.

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

LinkBack

Thread Tools

Display

Prime Numbers (difficult question about something seemingly simple)

Similar Math Help Forum Discussions

Simple Windows application to compute prime numbers

A Seemingly Simple Question Regarding the ratio of Two Gears

seemingly simple derivative

Help with a (seemingly?) simple proof.

Seemingly simple probability question...

Search Tags