Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complete residue system Question

  1. Feb 22, 2010 #1
    Hi i am doing self-study of number theory as it looks interesting and enlightening.
    Can someone help because I encounter a problem here..
    Suppose A = {a1,a1,,,,,,,ak} is a complete residue system modulo k. Prove that for each integer n and each nonnegative integer s there exists a congruence of the form
    n ≡ (sum j=0 to s)bj kj ( mod ks+1 )
    where bj[tex]\in[/tex] A for each j .
  2. jcsd
  3. Feb 22, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    a_1 and a_k are relatively prime, so you can use the extended Euclidean algorithm to find constants A and B with Aa_1 + Ba_k = 1. Then take (An)a_1 + (Bn)a_k.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook