Prime Numbers (difficult question about something seemingly simple)

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

Originally Posted by Bacterius

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

If you look at my post, I showed $10^a+1$ is composite for all $a\neq2^n$ (this is a stronger result). I suspect we can't go much further than this... These resemble Fermat numbers.

**Bacterius** · June 5th 2010, 09:09 PM

Originally Posted by chiph588@

If you look at my post, I showed $10^a+1$ is composite for all $a\neq2^n$ (this is a stronger result). I suspect we can't go much further than this... These resemble Fermat numbers.

Nice one, you just wiped some more numbers.
So let's resume. We eliminated :
All odd exponents : 1, 3, 5, 7, 9, ...
All exponents of the form $2m$ with $m$ odd : 2, 6, 10, 14, 18, 22, ...
All exponents of the form $2^n$ : 2, 4, 8, 16, 32, ...

We're still missing a small - yet infinite - subset of numbers, which can be expressed as $m = 12k$ , $k \in \mathbb{N}$ , that is, 12, 24, 36, ...

Am I right ?

**roninpro** · June 5th 2010, 09:33 PM

Originally Posted by Bacterius

Nice one, you just wiped some more numbers.
So let's resume. We eliminated :
All odd exponents : 1, 3, 5, 7, 9, ...
All exponents of the form $2m$ with $m$ odd : 2, 6, 10, 14, 18, 22, ...
All exponents of the form $2^n$ : 2, 4, 8, 16, 32, ...

We're still missing a small - yet infinite - subset of numbers, which can be expressed as $m = 12k$ , $k \in \mathbb{N}$ , that is, 12, 24, 36, ...

Am I right ?

I thought that the only candidates were numbers of the form $10^{2^k}+1$ . We did not eliminate them.

**Bacterius** · June 5th 2010, 09:34 PM

Originally Posted by roninpro

I thought that the only candidates were numbers of the form $10^{2^k}+1$ . We did not eliminate them.

Woops, I actually misread that. Sorry. I'll have a think.

**yeah:)** · June 6th 2010, 01:51 AM

WOW! I thought that this question would be considerably less difficult to solve...no wonder I was having problems!

**Bacterius** · June 6th 2010, 02:40 AM

Originally Posted by yeah:)

WOW! I thought that this question would be considerably less difficult to solve...no wonder I was having problems!

IHMO, if you see "Prime number" in a question, either the question is trivial, either it is excruciatingly difficult to prove.

**yeah:)** · June 6th 2010, 04:44 AM

Originally Posted by Bacterius

IHMO, if you see "Prime number" in a question, either the question is trivial, either it is excruciatingly difficult to prove.

Yes, that is true! Any 'brainy' ideas yet, Bacterius (or anyone, for that matter!)?

**Bacterius** · June 6th 2010, 05:20 AM

Originally Posted by yeah:)

Yes, that is true! Any 'brainy' ideas yet, Bacterius (or anyone, for that matter!)?

Nah, I'm off to sleep right now. Perhaps I'll get an idea while dreaming

**Bacterius** · June 6th 2010, 06:12 AM

Here's a start :

Let $10^{2^k} + 1 \equiv 0 \pmod{n}$ for some prime number $p$ , with $p \neq 10^{2^k} + 1$ .

So :

$10^{2^k} + 1 \equiv 0 \pmod{p}$

$10^{2^k} + 10 - 10 + 1 \equiv 0 \pmod{p}$

$10^{2^k} + 10 - 9 \equiv 0 \pmod{p}$

$10^{2^k} + 10 \equiv 9 \pmod{p}$

$10(10^{2^k - 1} + 1) \equiv 9 \pmod{p}$

$10^{2^k - 1} + 1 \equiv 9 \times 10^{-1} \pmod{p}$

$10^{2^k - 1} \equiv 9 \times 10^{-1} - 1 \pmod{p}$

Therefore, if $10^{2^k - 1} - 9 \times 10^{-1} + 1$ divides some $p$ in $\mathbb{Z}/p\mathbb{Z}$ , then $10^{2^k}$ is divisible by $p$ , thus is composite.

So we basically have to show that such a $p$ exists for all $k > 1$ . I'll give the proof that it doesn't exist for $k = 1$ .

Let $k = 1$ . Then, hypothetically, for some prime $p$ :

$10^{2^1 - 1} - 9 \times 10^{-1} + 1 \equiv 0 \pmod{p}$

$10 - 9 \times 10^{-1} + 1 \equiv 0 \pmod{p}$

$11 - 9 \times 10^{-1} \equiv 0 \pmod{p}$

Multiply by $10$ :

$110 - 9 \equiv 0 \pmod{p}$

$101 \equiv 0 \pmod{p}$

Which is only true for the prime number $101$ . However, $101 = 10^{2^1} + 1$ and we assumed that $p \neq 10^{2^k} + 1$ at the beginning, so we have a contradiction that leads to the conclusion that such a $p$ does not exist for $k = 1$ .

Anyone can prove that for any $k > 1$ exists at least one $p$ that satisfies the statement ?

**yeah:)** · June 6th 2010, 07:06 AM

100501 IS a prime number!

**roninpro** · June 6th 2010, 07:31 AM

Originally Posted by Bacterius

Here's a start :

Let $10^{2^k} + 1 \equiv 0 \pmod{n}$ for some prime number $p$ , with $p \neq 10^{2^k} + 1$ .

I'm having some trouble following you in the first line. Why would you want to assume that $p \neq 10^{2^k} + 1$ ? What if $10^{2^k}+1$ is prime itself?

Originally Posted by yeah:)

100501 IS a prime number!

I notice that you mentioned 100501 twice. What does this number have to do with the sequence 11, 101, 1001, 10001, ...?

**yeah:)** · June 6th 2010, 07:52 AM

You are right - it is completely irrelevant. I apologise about that.

**hmmmm** · June 6th 2010, 08:57 AM

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??

**yeah:)** · June 6th 2010, 10:37 AM

So do we have a definitive answer yet?

**gmatt** · June 6th 2010, 11:07 AM

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

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

LinkBack

Thread Tools

Display

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