Contents

a divides b, a|b. g-adic representation $a=\sum a_ng^n$.
$O(f(\thru n1k))$, polynomial time algorithms. Complexity of +, -, *, /, $\%$. Greatest common divisor $\gcd$. (Complexity of) the extended $\gcd$-algorithm.