Math Is Fun Forum

phanthanhtom

Member

Registered: 2012-06-22

Posts: 290

A problem with remainders modulo 2012

For a given pair of integer a and b (1<=a,b<2012, a =/= b), we define f(a,b) as the number of values for k (1<=k<2012) for which ak leaves a larger remainder than bk when divided by 2012. What is min f(a, b)?

Please provide the detailed solution. Thanks!

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,974

Website

Re: A problem with remainders modulo 2012

If a < b (mod 2012) shouldn't ka < kb (mod 2012)?

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

phanthanhtom

Member

Registered: 2012-06-22

Posts: 290

Re: A problem with remainders modulo 2012

No. When ka surpasses 2012, its remainder drops.

I found a solution anyway. http://math.stackexchange.com/questions/685173/2012-usajmo-problem-5

But I don't quite understand this part:

"So we want to maximize the times where ak≡0(mod2012) or ak≡bk(mod2012)

If k is even, then if a≡0(mod1006) or ak≡bk(mod1006)→a−b≡0(mod1006) we have a desired solution. So, we can make a=b+1006 or a=1006 to satisfy the second congruence for all even numbers. There are 1005 such even k.

Next consider the odd case for k. If k=503 or 3∗503 we just require a≡0(mod4) or a−b≡0(mod4), which we can easily satisfy. For all other k, we must have either ak≡0(mod2012) or a−b≡0(mod2012) which is impossible with the domain. Thus, 2 odd k work.

The minimum is then 1/2(2011−1005−2)=502. One value this is achieved at is f(1006,1010), though it works for all f(1006,4k+2) provided that the domain is considered."

Last edited by phanthanhtom (2015-06-26 02:00:40)

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,974

Website

Re: A problem with remainders modulo 2012

So this is a problem from USAJMO?

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.