Is there an integer divisible by 1989 with 1990 as its last four digits?

[philbein]

Homework Statement

Prove that there exists an integer divisible by 1989 Such that it's last four digits are 1990.

Homework Equations

Pigeonhole Principle where if we have k+1 items and k holes, two items go in one hole.

The Attempt at a Solution

Ok. I called my professor for help on this and I was given the hint that I should first take the integers from 1 to 1989, and multiply each one of them by 10^4. Then, when I divide each number, each has a different remainder, which means one of them has a remainder of one. I first need to figure out why this whole thing is true ( meaning why they each have different remainders). Then I need to figure out why it is important that one of these problems have a remainder of one. I have no clue on what to do here, so any suggestions would be great. Thanks for your time.

 

[tiny-tim]

Hi philbein!

Then I need to figure out why it is important that one of these problems have a remainder of one.

Try adding 1989 to it

 

[philbein]

Should I add 1989 to the remainder or to the orignal number that I had divided by 1989?

 

[tiny-tim]

erm …

if you're not sure, try both! ​

 

[philbein]

I'm sorry. I'm still not seeing what this does. Either way, I am still left with a remainder of 1.

 

[matt grime]

You've not quite got it right.

The point is that you have numbers ending in 4 noughts, and when you add 1990 you have a number ending in 1990. You've just got to show...

 

[philbein]

Ok. I'm still confused.

 

[Dick]

Ok. I'm still confused.

What you actually want is an n such that n*10^4 has a remainder of 1988 when divided by 1989. Since 1990 has a remainder of 1. So sure, if you have the 1989 numbers n*10^4 for n=1...1989 and the remainders are all different and each remainder is in the range 0...1988, then one of them must be 1988. The pigeonhole principle is used in proving that the remainders are all different. Suppose n1*10^4 and n2*10^4 have the same remainder. That means (n1-n2)*10^4 is divisible by 1989, right? But 10^4 and 1989 are coprime. They have no common prime divisors. What does that tell you?

 

[philbein]

Finally figured it out. Not an easy problem. Thanks for all the help. Couldn't have done it without the help. Thanks again.