Question

Let x be an integer of the form x = 111 . . . 111 with n “1s”. Show that if x is prime, then n
must also be prime.

Answer 1

Thinking out loud here, I think it's going to be easier to prove the contrapositive:
If n is not prime, then x = 1111.....111 (with n "1s") is not prime.

You can see that immediately if 2 is a factor of n, because for example if
x = 1111, then x = 11 * (101)
or if 3 is factor of n, then the sum of the digits of x is divisible by 3, which in turn means n is divisible by 3.

Of course we can't go through tests for every prime like this. So I'll have to think a little more tomorrow morning about how we can generalize.

Great problem; thanks for posting. I hope to have more to say soon.

Answer 2

Another observation. If x = 111...111 with n "1s" then
x = 1 + 10 + 10^2 + .... + 10^(n-1)
= ( 10^n - 1 )/9
Not sure how this helps yet, but it does formally get n into the expression for x.

Answer 3

thanks a lot for the reply James...

Answer 4

Ok, I think this works.

Note that in general for any natural number q > 1,
k^q - 1 = (k-1)[ 1 + k + k^2 + ... + k^(q-1) ]

Note also that for any natural number p that 10^p - 1 is divisible by 9.

Answer 5

that's the preliminaries, now ...

Answer 6

Suppose n is not prime. Then there are integers p, q > 1 such that
n = pq.

Thus we can write\[\frac{10^n - 1}{9} = \frac{10^{pq} - 1}{9} = \frac{(10^q)^p - 1}{9}\]
\[= \frac{10^q - 1}{9} . (1 + 10^q + 10^{2q} + ... + 10^{(p-1)q})\]
(I've flipped p and q notation from above, but no matter)
Now each one of these two terms is integral. Hence we have just written down a integral factorization of x and therefore x is not prime.
QED

Answer 7

wow...thats amazing..I am impressed...I will have to rhink through what you have done though...Good job and thank you..

Answer 8

Fun problem. What level course is this? Or is it from a competition paper?

Answer 9

yep...its a competition paper.. trying my hands on some of the problems

Answer 10

Hey James, what do you think about this one..For a real number x, ⌊x⌋ is defined to be the greatest integer less than or equal to x. Show
that
⌊n^1/2⌋ + ⌊n^1/3⌋ + ... + ⌊n^1/n⌋ = ⌊log2(n)⌋ + ⌊log3(n)⌋ + ... + ⌊logn(n)⌋
for n ≥ 2.

Answer 11

I'm tired and going to bed. But I'll come back to your new problem tomorrow. Happy solving!

Answer 12

ok man... Have a good night sleep and thanks for the help..