3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

$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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vladislav May 7 at 10:43
  • 1
    $\begingroup$ Well it seems to me that this exercise it way out of his league then. $\endgroup$ – zwim May 7 at 10:46
  • $\begingroup$ Unfortunately, it seems so $\endgroup$ – Vladislav May 7 at 10:52
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.