Euler’s Theorem

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

$$a^{\varphi (n)}\equiv 1(\text{mod }n)$$

where $\varphi (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}^{\varphi (3993)}\equiv 1(\text{mod }3993)$$

Therefore

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

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

$$3993|x$$

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

---