Euler’s Theorem

Euler’s Theorem states that for a positive integer $n$ and an integer $a$ relatively prime with $n$

$$ a^{\phi(n)} \equiv 1 \hspace{0.05in} (\text{mod } n) $$

where $\phi(n)$ is the Euler’s function.

Problem (Baltic Way, 1997)

If we add $1996$ to $1997$, we get $1996+1997=3993$, thus making three carries in total. Does there exist a positive integer $k$, such that adding $1996k$ to $1997k$ no carry arises during the whole calculation?

Solution

Answer: yes, there exists such a number $k$.

Let us prove that there exists a number $x$ that consists entirely of digits $9$ and is multiple of $3993$. This will automatically imply that if $x$ is a sum of some two numbers $1996k$ and $1997k$, then there were no carries during the calculation.

 

Since $10$ and $3993$ are relatively prime, then by Euler’s Theorem

$$ 10^{\phi(3993)} \equiv 1 \hspace{0.05in} (\text{mod } 3993) $$

Therefore

$$ 3993 \text{ } | \left( 10^{\phi(3993)} – 1 \right) $$

Now we can put $x=10^{\phi(3993)} – 1$. Note that $x$ consists entirely of digits $9$ and also

$$ 3993 \text{ } | \text{ } x $$

Now for the value of $k$ we can take the number $\phi(3993)$.

---