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. 
 A: 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.
A: 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)$$
A: Hint: Show that you can apply the Chinese Remainder theorem to 
$$x \equiv 0 \pmod {2009}\\x \equiv 1\pmod {1000000}$$
