# Prime Numbers (difficult question about something seemingly simple)

Show 40 post(s) from this thread on one page
Page 1 of 4 1234 Last
• Jun 5th 2010, 02:44 AM
yeah:)
Prime Numbers (difficult question about something seemingly simple)
• Jun 5th 2010, 06:51 AM
roninpro
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?
• Jun 5th 2010, 08:57 AM
yeah:)
So can anyone do part b)?
• Jun 5th 2010, 09:28 AM
chiph588@
Quote:

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
• Jun 5th 2010, 09:33 AM
undefined
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 AM
yeah:)
• Jun 5th 2010, 10:09 AM
undefined
Quote:

Originally Posted by yeah:)

You mean 10^100501 + 1? That returns composite.
• Jun 5th 2010, 03:41 PM
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}+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.
• Jun 5th 2010, 03:58 PM
tonio
Quote:

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
• Jun 5th 2010, 04:02 PM
chiph588@
Quote:

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.
• Jun 5th 2010, 05:12 PM
yeah:)
So, is there any definitive way of solving/proving part b)?
• Jun 5th 2010, 05:15 PM
chiph588@
Quote:

Originally Posted by yeah:)
So, is there any definitive way of solving/proving part b)?

Well, read my posts. It's being narrowed down.
• Jun 5th 2010, 05:21 PM
yeah:)
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 PM
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 :(
• Jun 5th 2010, 08:52 PM
Bacterius
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.
Show 40 post(s) from this thread on one page
Page 1 of 4 1234 Last