Difference between revisions of "2008 iTest Problems/Problem 48"

Revision as of 16:35, 16 September 2008

Problem

A repunit is a natural number whose digits are all $1$ . For instance,

$1,11,111,1111, \ldots$

are the four smallest repunits. How many digits are there in the smallest repunit that is divisible by $97$ ?

Solution

We have $\underbrace{111 \cdots 1}_{n\ \text{ones}} = 10^{n-1} + 10^{n-2} + \cdots + 1 = \frac{10^n - 1}{9}$ . Since $9$ and $97$ are relatively prime, it suffices for $10^{n} - 1 \equiv 0 \pmod{97}$ , or $10^{n} \equiv 1 \pmod{97}$ .

The smallest integer $m$ such that $a^m \equiv 1 \pmod{p}$ where $\text{gcd}\,(a,p)=1$ is $m = \lambda (p)$ , where $\lambda (p)$ is the Carmichael function. For primes $p$ , $\lambda(p) = p-1$ , and so the answer is $n = \boxed{96}$ .

Page

Toolbox

Search

Difference between revisions of "2008 iTest Problems/Problem 48"

Revision as of 16:35, 16 September 2008

Problem

Solution

See also