1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Write down a few multiples of $2009$. Maybe try the first $246889$ :P $\endgroup$
    – AlexR
    Mar 29 '15 at 17:22
  • $\begingroup$ 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. $\endgroup$
    – flabby99
    Mar 29 '15 at 17:24
  • $\begingroup$ @flabby99 Well, both hints in the answer work and boil down to the same. Another answer is hidden somewhere here ;) $\endgroup$
    – AlexR
    Mar 29 '15 at 17:26
  • $\begingroup$ @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 $\endgroup$
    – flabby99
    Mar 29 '15 at 17:27
  • $\begingroup$ @flabby99 It's from the extended euclidean algorithm to $\gcd(1000000,2009) = 1$. $\endgroup$
    – AlexR
    Mar 29 '15 at 17:28
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How to nuke-a-fly: Apply totient function where an efficient algorithm does your work ^^ $\endgroup$
    – AlexR
    Mar 29 '15 at 17:29
  • $\begingroup$ @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. $\endgroup$ Mar 29 '15 at 17:31
3
$\begingroup$

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)$$

$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$
    – flabby99
    Mar 29 '15 at 17:30
  • 1
    $\begingroup$ @flabby99 Yes, perfect! The extended one will even provide you with $k$ for free. $\endgroup$
    – AlexR
    Mar 29 '15 at 17:30
  • $\begingroup$ @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$ $\endgroup$
    – Mathmo123
    Mar 29 '15 at 17:39
  • $\begingroup$ @Mathmo123 I must admit, I am missing how the proof follows just from observing that 2009 is not divisible by 2 or 5. $\endgroup$
    – flabby99
    Mar 29 '15 at 17:48
  • 2
    $\begingroup$ @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$ $\endgroup$
    – Mathmo123
    Mar 29 '15 at 17:49
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +1. Only flabby99 can tell us if this problem is in his textbook after a discussion of the Chinese Remainder Theorem. $\endgroup$
    – GEdgar
    Mar 29 '15 at 17:43
  • $\begingroup$ 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. $\endgroup$
    – flabby99
    Mar 29 '15 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.