The positive integer $N = 11...11$, whose decimal representation contains only ones, is divisible by $7$. Prove that this positive integer is also divisible by $13$.
Problem
Source:
Tags: number theory, divisible, Digits, divides
Andrew_Dou
15.11.2021 17:41
$N=\sum_{k=0}^n 10^k=\frac{10^{n+1}-1}{9}.$ Since $\text{gcd}(7,9)=1,$ for $7 \mid N,$ we must have $ 7 \mid 10^{n+1}-1.$
Note that $10^{\phi(7)} \equiv 10^6 \equiv 1 \pmod{7},$ and it can be manually checked $\text{ord}_{7}(10)=6.$ Hence, $n=6m-1$ for integers $m>0.$
Now, note that $\text{gcd}(13,9)=1$ so $13 \mid N$ when $13 \mid 10^{n+1}-1.$
We have that $10^{\phi(13)}=10^{12} \equiv 1 \pmod{13},$ and it can be checked that $\text{ord}_{13}(10)=12.$ Hence, for $13 \mid N,$ we have $n=12k-1=6(2k)-1$ for integers $k>0,$ which is in the form $6m-1,$ so we are done.
RANDOMMATHLOVER
15.11.2021 19:51
We can break $N$ into blocks of $6$ $1$s starting from the left. We note that $111111$ is divisible by $7,$ so if the rightmost block has $k$ digits where $0<k<6$ we have a contradiction, as a k-digited number with $1$s only is never a multiple of $7.$ So $k=6$ and it follows that $N$ has $6t$ $1$s for some positive integer $t,$ which means $N$ is divisible by $111111$ and thus also by $13,$ since $13\mid 111111.$