a - b I |
(12) |

usually denoted by

a b mod I |
(13) |

defines an equivalence relation. If we denote by (or if not ambiguous) the class of the element

+ = and = |
(14) |

p | a - b p | (q_{a} - q_{b})p + r_{a} - r_{b} p | r_{a} - r_{b} |
(15) |

a b mod p r_{a} = r_{b} |
(16) |

a = q(x - u) + a(u) |
(17) |

a b mod p a(u) = b(u) |
(18) |

s a + t m = g |
(19) |

If

a b 1 mod m |
(20) |

That is there exists

ResidueClassRing(R:EuclideanDomain, p:R): Ring with { class: R -> %; sample: % -> R; } == R add { Rep == R; import from R; 1: % == per(1); 0: % == per(0); zero?(x:%): Boolean == zero?(rep(x)); (x:%) = (y:%) : Boolean == zero?(x-y); one?(x:%): Boolean == x = 1; class(a:R):% == { (q,r) := divide(a,p); per(r); } sample(x:%): R == rep(x); (x:%) + (y:%) : % == class(rep(x) + rep(y)); -(x:%) : % == class(-rep(x)); (x:%) * (y:%) : % == class(rep(x) * rep(y)); (n:Integer) * (x:%): % == class(n * rep(x)); (x:%) ^ (n:NonNegativeInteger) : % == class(rep(x) ^ n); recip(x:%): Partial(%) == { import from Partial(%); (u,v,g) := extendedEuclidean(rep(x),p); h?: Partial(R) := recip(g); failed? h? => failed(); h: R := retract(h?); [class(h * u)]; } }

(/m)^{ * } = {a mod m | gcd(a, m) = 1} |
(21) |

(m) = (p - 1)p^{e-1} |
(22) |

a^{p} a mod p |
(23) |

Moreover if

a^{p} = ((a - 1) + 1)^{p} (a - 1)^{p} + 1^{p} (a - 1) + 1 = a mod p |
(24) |

a^{-1} a^{p-2}mod p |
(25) |

2003-06-06