Proof (continued) Equivalently, we have ∑a(x-y)=0(modm) or ao(o-yo)+2a(x-y)=0(mod m) which implies that 10(o-yo)=->a, (x-Vi)(mod m) o 2001 by Charles E Leiserson Introduction to Algorithms Dav12L8.12© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.12 Proof (continued) Equivalently, we have ( ) 0 (mod ) 0 a x y m r i ∑ i i − i ≡ = or ( ) ( ) 0 (mod ) 1 a0 x0 y0 a x y m r i − +∑ i i − i ≡ = ( ) ( ) (mod ) 1 a0 x0 y0 a x y m r i ∑ i i i = − ≡ − − which implies that ,