Remainder

[stuart clark]

Find Remainder when 2008²⁰⁰⁷-2008 is divided by 2008²+2009

[proble_m]

Since 2008²+2009 = 2008²+2008+1 and x³-1=(x-1)(x²+x+1) we can write
2008³=2007(2008²+2009)+1.
So,
2008²⁰⁰⁷-2008 =(2008³)⁶⁶⁹-2008 =  (2007(2008²+2009)+1)⁶⁶⁹-2008
now for mod(2008²+2009) this becomes
(2007(2008²+2009)+1)⁶⁶⁹-2008≡1-2008(mod(2008²+2009))
≡-2007(mod(2008²+2009))
≡-2007+2008²+2009(mod(2008²+2009))
≡2008²+2(mod(2008²+2009))

[stuart clark]

Thanks proble_m