Prove that, among $100000$ consecutive $100$-digit positive integers, there is an integer $n$ such that the length of the period of the decimal expansion of $\frac1n$ is greater than $2011$.
Problem
Source: XVIII Tuymaada Mathematical Olympiad (2011), Junior Level
Tags: Euler, quadratics, number theory unsolved, number theory
30.07.2011 06:55
26.08.2011 13:57
let's talk about the period of $ 1/n $ : 1. $ (n,10)=1 $ then the period has the length $ w $ where $ 10^{w}-1 $ is divisible by $ n $ and $ w $ is minimum. 2. $ n=2^{a}*5^{b}*m $ and $ (m,10)=1 $ then the period is divisible by $ w $ where $ 10^{w}-1 $ is divisible by $ m $ and $ w $ is minimum. let take $ x=29*23*19=12673<100000 $ then the number $ w $ for this number is $ 11*28*9=2772 $ because: 1. $ n_{1}=19 $ then $ w_{1}=18 $. 2. $ n_{2}=23 $ then $ w_{2}=11 $. 3. $ n_{3}=29 $ then $ w_{3}=28 $. we prove these ones using Euler and quadratic residues. then between the $ 10^{5} $ consecutive numbers exist one divisible by $ x $. this one is the number with the property that $ 1/n $ has the period of length greater than $ 2011 $. q.e.d.
27.08.2011 17:08
Because $10$ is a primitive root of $49$, so $10$ is also a primitive root of ${7^4}=2401$, hence the order of $10$ for ${7^4}$ is $\varphi \left( {{7^4}} \right) = {7^3} \times 6 = 2058 > 2011$. Among any $2500$ consecutive positive integers, there is an integer ${7^4}\left| n \right.$, so the length of the period of the decimal expansion of $\frac{1}{n}$ is greater than $2011$.
26.11.2011 07:05
it suffices to prove that there exists an $n$,the order of $10$ mod $n\ge 2012$ among any $100000$ consecutive iuntegers there is a multiple of $4079$,and $O_{10}(4079)|4078$,hence it equals to $2039$ or $4078$,proved.
22.09.2016 06:04
A very cute example. Let us write $$ \frac{1}{n}=0.a_1a_2\dots a_k \dots $$in the decimal expansion where $k$ denotes the length of the periodic part of the number. We note that this yields $$ \frac{10^k-1}{n}= {a_1a_2\dots a_k} $$and we have $n \mid 10^k-1$. Now, consider $N=7^4=2401<<10^6$ and note that $\text{ord}_7(10)=6$ and so for $k \le 2011$, we have $k<6\cdot 7^3$. By lifting the exponent lemma, $v_7(10^k-1)=v_7(10^6-1)+v_7(k)<4$ and we conclude that $7^4 \nmid 10^k-1$. Now, $2401$ divides some number among $10^6$ consecutive natural numbers and since $\frac{1}{2401}$ has a periodic part of length more than $2011$, we may conclude.