# Prove that there is a multiple of 2009 that ends with the digits 000001

Prove that there is a multiple of 2009 that ends with the digits 000001.

May one generalise this to: There exists a multiple of $x$ that ends with the digits $y$ (where $y$ consists of $n$ digits) if $x$ and $10^n$ are relatively prime?

The proof may be constructive, or non constructive.

Any help would be greatly appreciated.

I figured the multiple has to end in a $9$: $2009 \cdot 889$ gives $001$ as the three ending digits. I then tried to see if I could get the $4$th last digit to be a zero, but I must admit I am clearly missing something at that point.

• Write down a few multiples of $2009$. Maybe try the first $246889$ :P Mar 29 '15 at 17:22
• Well it needs to end in a one, so I figured the multiple has to end in a 9. 2009 * 889 gives 001 as the three ending digits. I then tried to see if I could get the 4th last digit to be a zero, but I must admit I am clearly missing something at that point. Mar 29 '15 at 17:24
• @flabby99 Well, both hints in the answer work and boil down to the same. Another answer is hidden somewhere here ;) Mar 29 '15 at 17:26
• @AlexR Yes I see that there is some magical number within these comments. However, I would like to understand better how to obtain such a magic number :P Mar 29 '15 at 17:27
• @flabby99 It's from the extended euclidean algorithm to $\gcd(1000000,2009) = 1$. Mar 29 '15 at 17:28

## 3 Answers

Here is a short proof using modular arithmetic.

Consider $m=1000000$. The numbers $2009$ and $m$ are relatively prime to each other, so

$$2009^{\phi(m)}\equiv 1\pmod m$$

where $\phi(m)$ is the count of the numbers between $1$ and $m$ that are relatively prime to $m$. $2009$ divides $2009^{\phi(m)}$ so that proves your statement.

Of course, this is not the smallest such multiple of $2009$. To find that, use the extended Euclidean algorithm on $2009$ and $1000000$.

As I wrote, the key is that $2009$ and $1000000$ are relatively prime.

• How to nuke-a-fly: Apply totient function where an efficient algorithm does your work ^^ Mar 29 '15 at 17:29
• @AlexR: The OP just asked for a proof, not an efficient algorithm. Anyway, I modified my post (before I saw your comment) to also refer to that algorithm. The OP can decide which is better suited to his purpose. Mar 29 '15 at 17:31

Hint
You must show that there exists $k$ such that $$2009 k \equiv 1 \pmod{1000000}$$ i.e. that $2009$ has a multiplicative inverse in $\mathbb Z_{1000000}^\times$. Do you know of some criteria?

If you want to obtain $k$, the easiest way is the extended euclidean algorithm on $1000000$ and $2009$. It will give you numbers $x,y$ such that $$2009 x + 1000000 y = \gcd(1000000,2009)$$

• 2009 must be relatively prime to 1000000 ( to satisfy the mentioned criteria). The Euclidean algorithm should handle that without too much difficulty. Is my thought process correct? Mar 29 '15 at 17:30
• @flabby99 Yes, perfect! The extended one will even provide you with $k$ for free. Mar 29 '15 at 17:30
• @flabby99 if you are just looking for a non constructive proof, even the Euclidean algorithm is overkill - just observe that $2009$ is not divisible by $2$ or $5$ Mar 29 '15 at 17:39
• @Mathmo123 I must admit, I am missing how the proof follows just from observing that 2009 is not divisible by 2 or 5. Mar 29 '15 at 17:48
• @flabby99 this is just a faster way of showing the numbers are relatively prime, since $1000000$ is divisible by only the primes $2$ and $5$ Mar 29 '15 at 17:49

Hint: Show that you can apply the Chinese Remainder theorem to $$x \equiv 0 \pmod {2009}\\x \equiv 1\pmod {1000000}$$

• +1. Only flabby99 can tell us if this problem is in his textbook after a discussion of the Chinese Remainder Theorem. Mar 29 '15 at 17:43
• It is a general problem from elementary number theory from an optional set of problems by one of my lecturers, and may be solved using whatever is within our grasp. I am however, aware of the Chinese Remainder Theorem. I just failed to see it's application in this situation. Mar 29 '15 at 17:50