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, 2015 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, 2015 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, 2015 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, 2015 at 17:27
  • $\begingroup$ @flabby99 It's from the extended euclidean algorithm to $\gcd(1000000,2009) = 1$. $\endgroup$
    – AlexR
    Mar 29, 2015 at 17:28

3 Answers 3

Reset to default
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, 2015 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$
    – Rory Daulton
    Mar 29, 2015 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, 2015 at 17:30
  • 1
    $\begingroup$ @flabby99 Yes, perfect! The extended one will even provide you with $k$ for free. $\endgroup$
    – AlexR
    Mar 29, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 17:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .