BASIC PROPERTIES OF CONGRUENCES

1 BASIC PROPERTIES OF CONGRUENCESThe lettersa, b, c, d, krepresent integers. The lettersm, nrepresent positive integers. Thenotationa b(modm) means thatmdividesa b. We then say thatais congruent (Reflexive Property):a a(modm)2. (Symmetric Property): Ifa b(modm), thenb a(modm).3. (Transitive Property): Ifa b(modm) andb c(modm), thena c(modm).Remark:The above three PROPERTIES imply that (modm) is an equivalence relationon the Ifa b(modm) andc d(modm), thena+c b+d(modm) anda c b d(modm).5. Ifa b(modm) andc d(modm), thenac bd(modm).6. Assume thata b(modm). Letk 1. Thenak bk(modm).7. Suppose thatP(x) is any polynomial with coefficients inZ. Assume thata b(modm).ThenP(a) P(b) (modm).8. Assume thata b(modm). Thengcd(a, m) =gcd(b, m).9. Ifa b(modm) andn|m, thena b(modn).

2 10. Assume thatgcd(m, n) = 1. Assume thata b(modm) and thata b(modn). Thena b(modmn).11. Suppose thata Z. Then there exists a unique integerrsuch thata r(modm) and0 r m 1. This integerris the remainder whenais divided Assume thatca cb(modm) and that (c, m) = 1. Thena b(modm).13. Assumepis a prime. Ifab 0 (modp), then eithera 0 (modp) orb 0 (modp).14. Assume thatpis a prime and thatp-a. Thenap 1 1 (modp).