1
$\begingroup$

A repunit of length k is a number containing k ones (1, 11, 111...).

R(k) is defined to be the repunit of length k.

A(n) is the least value of k such that R(k) is divisble by n (assuming gcd(n, 10) = 1).

Reading online, several articles claim that A(n) < n, but no explanation is given (and that's why I'm assuming I'm missing something obvious...), and I don't understand how that inequality came to be. An explanation on why that inequality holds would be very appreciated.

$\endgroup$
  • $\begingroup$ You shouldn't assume that people here will know what's a "repunit" $\endgroup$ – fonini Jul 1 '15 at 19:59
  • $\begingroup$ By the way, I wouldn't mention that this has to do with proj euler at all, because now people searching google for "proj euler NNN" will find this. (and folks at projecteuler dot net ask you specifically not to do this) $\endgroup$ – fonini Jul 1 '15 at 20:00
  • $\begingroup$ You are right, I removed references to that place. Sorry about this. $\endgroup$ – Ashura Jul 1 '15 at 20:04
0
$\begingroup$

Note that if $\gcd(10,n)=1$, then by the Euler-Fermat theorem we have $$10^{\varphi(n)} \equiv 1 \mod n$$

Therefore $$10^{\phi(n)}-1 \equiv 0 \mod n$$

$$n \mid 10^{\varphi(n)}-1$$

Therefore $$n \mid \underbrace{999...999}_{\varphi(n)}$$ $$n \mid R(\varphi(n))$$

And for $n>1$ we have $\varphi(n) < n$.

$\endgroup$
  • 1
    $\begingroup$ You can say $n\mid 9R(\phi(n))$, but not $n\mid R(\phi(n))$, unless $\gcd(n,3)=1$ (as Syd Henderson notes). $\endgroup$ – Barry Cipra Jul 1 '15 at 20:13
  • $\begingroup$ Together with Barry/Syd's comment, I understand now :) $\endgroup$ – Ashura Jul 1 '15 at 20:14
  • $\begingroup$ You are welcome. $\endgroup$ – wythagoras Jul 1 '15 at 20:15
1
$\begingroup$

It's also not true for powers of 3.

$\endgroup$
1
$\begingroup$

The correct claim is $A(n)\le n$, which can be proved by the pigeonhole principle. The set of $n$ numbers $\{1,11,111,\ldots,111...11\}$ either exhausts the remainders mod $n$, in which case the one with remainder $0$ is divisible by $n$, or else, by the pigeonhole principle, two of them have the same remainder, in which case their difference is divisible by $n$. But the difference of two repunits is of the form $111\ldots11000\ldots00$, at which point one invokes the assumption $\gcd(n,10)=1$ to conclude that $n$ divides the opening repunit in that difference.

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