Let $O_n = \underbrace{111111\ldots1}_{\text{ number of 1's }=\, n}.$

Find the smallest positive integer $n$ such that $2017 \mid O_n$ .

If there is no such $n$ , enter 0.

The answer is 2016.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

"We have to (tediously) check the values."

How did you do it? I can't think of an easy way to do so TT.TT

Manuel Kahayon
- 4 years, 4 months ago

Log in to reply

I did it tediously. It is direct to do, but it just requires a lot of calculations in mod. I would recommend repeated squaring as a fast way to get the answer.

If you understand how to do this, and do not need the practice, then yes wolfram could calculate it immediately.

I would use a Modular Exponentiation Calculator; there are plenty of them online.

Muhammad Rasel Parvej
- 4 years, 4 months ago

Pretty neat, I must say! Thanks!

Muhammad Rasel Parvej
- 4 years, 5 months ago

$O_n= \overline{111\cdots{ } \cdots{ } \cdots{ }11} \\ =\dfrac{10^n-1}{9}$

Using Euler's Totient Function $\phi (2017)=2016$ as $2017$ is a prime number.

So, $10^{2016} \equiv 1 \pmod{2017}$ as $gcd(10,2017)=1$

Again $10^{2016} \equiv 1 \pmod{9}$

It can be written as $10^n-1$ is both divisible by $2017$ and $9$

Therefore , $10^{2016} -1=9 \times 2017 l$ where $l \in Z^+$

$\dfrac{10^{2016} -1}{9}=2017 l \implies 2017 | \dfrac{10^{2016} -1}{9}$

So, the smallest $n=2016$

1 Helpful
0 Interesting
0 Brilliant
0 Confused

This solution is incomplete.

Remember that if a number is a minimum, it has to satisfy 2 conditions.

1. It is a lower bound.

2. It can be achieved.

You have shown that 2) It can be achieved. However, how do we know that there is no smaller number that would work?

As an explicit counter example, if we replaced 2017 by 11, then the answer isn't $11 - 1$ , even though $11 \mid \frac{ 10 ^ {10 } - 1 } { 9}$ (can be achieved). Instead, the answer is 2, with $N_n = 11$ (so 10 isn't a lower bound).

Log in to reply

But how I will show that 2016 is the lower bound ???

Kushal Bose
- 4 years, 5 months ago

Log in to reply

It would take work. Essentially, you are asked for the Order of 10 mod 2017.

Log in to reply

@Calvin Lin – Any hint u can provide ?

Kushal Bose
- 4 years, 5 months ago

Log in to reply

Log in to reply

@Calvin Lin – Ok I will try

Kushal Bose
- 4 years, 5 months ago

Log in to reply

@Kushal Bose – A simple way to fix this is to recall the Carmichael's Lambda function .

Pi Han Goh
- 4 years, 5 months ago

Log in to reply

@Pi Han Goh – Can you elaborate further? I'm not sure that approach would work.

The Carmichael Lambda function is a global property (about all $a$ where $\gcd(a,2017) = 1$ ), whereas we're looking for a local property (where $a = 10$ ).

E.g. If we wanted to find the smallest $n$ such that $1^{n} \equiv 1 \pmod{2017}$ , I don't see how knowing $\lambda (2017)$ would affect the answer.

Log in to reply

@Calvin Lin – Sorry, I misinterpreted the function again. I'm back to square one again... = (

Pi Han Goh
- 4 years, 5 months ago

Having a look at other solutions and comments, I got to know about a counter example of 11. Indeed, 11 divides (10^2 - 1) / 9 but it is as much fault of the power of 10 as it is of 11 itself. You see, 11 = 10 + 1 and that opens a whole new chain of divisibility taking advantage of the relationship between the terms (a^n - 1) and (a + 1).

It is safe to assume that 11 is an exception rather than the rule. Further examination required.

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

Observe that $O_n = \frac{ 10^n - 1 } { 9 }$ . Since $\gcd (9, 2017) = 1$ , hence we are looking for the smallest $n$ such that $10^n \equiv 1 \pmod{2017}$ . Denote this number by $N$ . This is also known as the order of 10 mod 2017.

From Fermat's little theorem , since 2017 is a prime, hence we know that $10 ^ { 2016 } \equiv 1 \pmod {2017}$ . This establishes that $N \leq 2016$ (IE 2016 can be achieved). We will show that $N = 2016$ by proving that no smaller number will work (IE 2016 is a lower bound).

Claim:$N \mid 2016$ .Proof:Let $2016 = Nq + r$ , where $0 \leq r < N$ .Then $1 \equiv 10^{2016} \equiv 10^{Nq} \times 10^r \equiv 10 ^ r \pmod{2017}$ . Since $N$ is the smallest positive integer such that $10 ^N \equiv 1 \pmod{2017}$ , this shows that $r$ is not a positive integer so $r = 0$ . Hence $2016 = Nq$ as desired. $_\square$

Claim:$2016 = 2^5 \times 3^2 \times 7$ . If for $M = \frac{2016}{2}, \frac{2016}{3}, \frac{2016}{7}$ , we have $10 ^ M \not \equiv 1 \pmod{2017}$ , then $N = 2016$ .Proof:Since $N \mid 2016$ , suppose that $N \neq 2016$ . Then $N$ must divide (at least) one of the values of $M$ . For that chosen value, let $M = Nq$ . Then, $1 \equiv 10^{Nq} \equiv 10^m \not \equiv 1 \pmod{2017}$ which is a contradiction. $_\square$Claim:For $M = \frac{2016}{2}, \frac{2016}{3}, \frac{2016}{7}$ , then $10 ^ M \not \equiv 1 \pmod{2017}$ .Proof:We have to (tediously) check the values. We obtain:$10 ^{1008} \equiv 2016 \pmod{2017},$

$10 ^{672} \equiv 294 \pmod{2017},$

$10 ^{288} \equiv 79 \pmod{2017}$ . $_\square$

Note: The above shows that 10 is a primitive root of 2017. Unfortunately, there isn't an easy general way to show that a number is a primitive root, other than checking in the manner that we did.

(Calvin's rant about minimum)

Remember that when we say $N$ is a minimum, it must satisfy both of the following conditions:

1. It is a lower bound.

2. It can be achieved.

In this case, condition 2 is easy to check, and condition 1 requires work.