Skip to main content

Integer Arithmetic Contracts

All lab arguments are integers, excluding booleans; type coercion is outside this exercise. Signed a and b are supported.

  • gcd(a,b): nonnegative result; gcd(0,0)=0 by convention.
  • extended_gcd(a,b): (g,x,y) with a*x+b*y=g; coefficients may differ between correct implementations.
  • inverse(a,m): m>1 and gcd=1; canonical inverse, otherwise ValueError.
  • solve_congruence(a,b,m): m>0; sorted complete list in [0,m). No solution returns []; invalid modulus raises. For a=0, every residue or none is possible; for m=1 the list is [0].
  • power_mod(a,e,m): e>=0, m>0; zero exponent gives 1 % m. Invalid domain raises.
  • is_prime(n): false below 2; trial division includes the square-root boundary.

The positive-integer modulus convention is deliberate. Never infer remainder behavior in another language from a Python experiment alone. Consult the source reading guide for mathematical definitions and the lab README for implementation restrictions.