P Ones

Number Theory Level 2

Find the sum of all prime numbers $p$ that divides $\underset{\text{the digit 1 is repeated }p \text{ times}}{\underbrace{111111111111111\cdots 1}}$ .

The answer is 3.

3 solutions

Happy Melodies
Jun 21, 2015

Edited Solution Intuition: $\underbrace{(111 \ldots 1)}_p =10 ^{p-1} + 10^{p-2} + \ldots + 10 + 1$ Next notice: $10 ^{p-1} + 10^{p-2} + \ldots + 10 + 1 = \frac{10^p -1}{9}$ By Fermat's Little Theorem ( $a^p \equiv a \pmod p$ ), we have $10^p-1 \equiv 10 -1 = 9 \pmod p$ .

Then, it follows that: $\frac{10^p -1}{9} \equiv 1 \pmod{p} \ \forall p: \gcd(p,9) = 1$ .

The only possible prime that satisfies $\gcd(p,9) \neq 1$ is $\boxed{3}$ . Checking this case, we see that indeed $3$ divides $111$ and we are done!

Special thanks to @Prasun Biswas for pointing out the errors in my previous solution.

Your second equation should have RHS as $\dfrac{10^p-1}9$ . Also, it should be Fermat's Little Theorem, not Last (in your conclusion). Fermat's Last Theorem is a completely different theorem.

Here's how the Fermat's Little Theorem argument works.

We have, by FLT and basic modular arithmetic,

$10^p\equiv 10\pmod{p}\implies 10^p-1\equiv 9\pmod{p}\\\implies\frac{10^p-1}{9}\equiv 1\pmod{p}~~\forall~p:\gcd(p,9)=1$

And the only prime for which $\gcd(p,9)\neq 1$ is $p=3$ . Check this case manually using the divisibility rule for $3$ and you see that $p=3$ indeed works and is hence the only prime solution.

The conclusion follows the same as in your solution.

You can use a similar approach to try out this proof problem (Q-4) here .

Prasun Biswas - 5 years, 11 months ago

Why does the greatest common divisor of p and 9 have to be 1 in order for that congruence to work?

Ραμών Αδάλια - 4 years, 12 months ago

@Ραμών Αδάλια @Puneet Pinku, the reason for that is because, in modular arithmetic, division by a number $x$ is well-defined (valid) for a congruence when $x$ and the congruence modulus are coprime. You can see that this is true because modular multiplicative inverse of an element exists iff it's coprime with the modulus.

When they are not coprime, the division might result in an incorrect congruence. For example, consider $5\equiv 15\pmod{10}$ which is true but division of both sides by $5$ gives $1\equiv 3\pmod{10}$ which is obviously false.

Another way you can see why they should be coprime is by means of the following theorem:

Theorem: Let $a,b$ be two integers divisible by an integer $x\neq 0$ and let $n$ be a positive integer. Then, the following congruence holds:

$a\equiv b\pmod{n}\iff a/x\equiv b/x\pmod{n/\gcd(x,n)}$

For our case, we need the modulus to be $n$ , so we set $\gcd(x,n)=1$ , i.e., consider only those $x$ 's which are coprime to $n$ . For a proof of the above theorem, see this .

Prasun Biswas - 4 years, 11 months ago

Just saw this post! You are right and I realised how messed up my solution is ... (Can't imagine how I put it as Fermat's Last Theorem instead of Little but I knew that haha.) Thank you for correcting me! :)

Happy Melodies - 5 years, 10 months ago

Why should the gcd of (p,9) be 1?

Puneet Pinku - 5 years ago

There are many primes that divide 111...1. For example: 3|111, 11|1111, 41|11111, 239|1111111, etc. Do these not matter?

Kelly Waters - 5 years, 7 months ago

The problem says that $p\mid\underbrace{\overline{11\ldots 11}}_p$ (notice the underbrace) , hence the number of $1$ 's in the corresponding repunit must be $p$ too.

Only the case of $p=3$ satisfies the problem criterions since $111$ has 3 1's and $3\mid 111$ . The rest of the cases you mentioned don't have the number of 1's in the corresponding repunit equal to $p$ . For example, $11\mid 1111$ but $1111$ has 4 1's, not 11 1's.

Prasun Biswas - 5 years, 7 months ago

agree that 3 works, but id it the only prime? doesn't 1 work as well? (1 is prime and divises itself, no?)

Alexis Vlr - 4 years, 8 months ago

1 is not a prime

Sean Tremba - 2 years, 10 months ago

I have to say the meaning of the question was unclear until I read the answer. P isn't the number, and it's not the base in which the number is expressed, it's the number of digits in the number? I feel like I spent more time reading the question than was spent writing it, or at the least, not much effort would be required to phrase it clearly. Hopefully this app doesn't habitually waste people's time.

Ban Yan - 3 years, 11 months ago

17 works as well? 17*653594771824183 = 11 111 111 111 111 111

Unless I messed up my long division?

Ashley Reavis - 5 years, 3 months ago

Yup, you messed up your long division. My calculator shows that,

$\frac{11111111111111111}{17}\approx 653594771241830.05882353$

Prasun Biswas - 5 years, 3 months ago

But 11 also satisfies.

Aaryaman Gupta - 5 years, 8 months ago

No it does not. The equation is asking a prime that divides perfectly the length of the number equal to p. 11 does not satisfy because:

11111111111 mod 11 ≠ 0. Notice the length p of the integer is 11 which is not dividing the number. Thus 3 is the only solution possible, by divisibility rule. Read posts by Prasun biswas who as explained it well above.

Nitin Mishra - 5 years ago

11 111 111 111 : 11 = 1 010 101 010 And 13 also works.

Ragnhild Kjøsnes - 5 years, 5 months ago

11 does not satisfy. For numbers consisting only of one's eleven only divides them if there is an even number of ones. The equation is asking for numbers that evenly divide.

Miles Johnson - 5 years, 3 months ago

This was a terribly worded question. I thought i was asking for the sum of primes from the set {1, 11, 111, 1111, etc} I have never seen the | notation like used in the problem. I came here to learn but frustrated by poorly worded problems

Richard Allred - 3 years, 6 months ago

Daniela Perlini
Sep 20, 2018

Let $a$ be $(111...1)$ . It's clear that $a=a\times 10 + 1 -10^{p}$ where $p$ is the number of digits $1$ that build $a$ .

Since $10^p\equiv 10 \pmod p$ (for Fermat's Little Theorem), the following equation is true: $9a+1=10^{p}\equiv 10 \pmod p$

We then can deduce that

$9(a-1)\equiv 0 \pmod p$

For the zero-product property we have that $p|9 \vee p|a-1$ .

If $p|a-1$ then clearly $p\nmid a$ , so $\nexists p$ such that $p| (111...1)$ and $p|(111...0)$ . Therefore $p|9$ : that is true only if $p=3$ .

Now I only need to verify that it's actually true that $3|111$ , which it is. So the "sum" of all prime numbers such that $p|(111...1)$ is $3$ .

Leonhard Euler
Feb 24, 2020

Suppose $p$ divides $\underbrace{111\ldots 1}_{p}$ . Then $p$ also divides $\underbrace{999\ldots 9}_{p} = 10^{p}-1$ .

In other words $10^{p}-1\equiv 0 \pmod{p}$ .

By Fermat's Little Theorem, we know $10^{p}\equiv 10\pmod{p}$ .

Therefore $9\equiv 0 \pmod{p}$ , which can only be true for $p=3$ , if $p$ is a prime.

Since $3$ is a prime factor of $111$ , the only prime number $p$ such that $p|\underbrace{111\ldots 1}_{p}$ is $\boxed{p=3}$ .

Thank you sir,thsi is much better neat and clean explanation

majoj pradhani - 8 months, 3 weeks ago

P Ones

The answer is 3.

3 solutions

0 pending reports