# School-level problem on divisibility

I encountered the problem to show that there is an integer of the form $$11111\ldots 11$$ divisible by $$2021$$. It is easy to show that there is a number of the form $$111 \ldots 11 \cdot 10^k$$ divisible by $$2021$$. But I can't use the unique factorisation to get rid of $$10^k$$ (the problem says no unique factorisation). So how can I prove that?

$$18189=9\times 2021$$ is relatively prime with $$10$$.

So there exists $$k$$ such that $$10^k\equiv 1\pmod{18189}$$

$$k=966=(2)(3)(7)(23)$$ can be tested from divisors of Euler totient function $$\phi(18189)=(2)^3(3)^2(7)(23)$$.

Thus the repunit $$\frac 19(10^k-1)$$ is divisible by 2021.

• It is actually a homework of a 10-year-old kid, he cannot prove that something is relatively prime to something not using unique factorisation. He doesn't know the Euclidian algorithm yet. – Vladislav May 7 at 10:43
• Well it seems to me that this exercise it way out of his league then. – zwim May 7 at 10:46
• Unfortunately, it seems so – Vladislav May 7 at 10:52

For every natural number $$m$$($$m$$ is co prime to $$2$$ and $$5$$), there is a respective string of $$1$$ , that is $$1111...11$$ which is divisible by $$m$$.

Proof: For, some number $$n$$, we know $$n|10^{\phi(n)}-1$$, from Euler's theorem.

We can write any number which is a string of $$1$$s$$(11111....)$$ in base $$10$$ as $$1+10^{1}+10^{2}+....10^{a-1}=\frac{10^{a}-1}{9}$$

Now, if $$\text{gcd}(n,9)=1,$$ we can put $$a=k\phi(n)$$ without any hesitation. Because the $$9$$ in denominator will not take out any factor common with $$n$$.

But, if $$\text{gcd}(n, 9)≠1$$, then $$n=3^{l}p$$. And we can easily show that the power of $$3$$ in $${10^{k\phi(n)}-1}$$ is more than $$l+1$$ for all $$k>k_0$$ for some $$k_0>1.$$

And this way we have proved the statement to be true. And even by this algorithm you can make such strings.

There may be more other strings of $$1$$ for few $$n$$s. I mean other than this algorithm.