Skip to main content

Proof and Trace Practice

  1. Give Euclidean quotient/remainder pairs for -23 and 23 divided by 7; justify uniqueness.
  2. Trace gcd(84,30), write a Bezout certificate and adapt it to signed inputs.
  3. Prove that (a,b) and (b,a-qb) have the same common divisors. Separately give a decreasing nonnegative quantity for termination.
  4. Factor 90 and 126 and recover their gcd from shared prime factors. Explain why you would still use Euclid operationally.
  5. Find the inverse of 11 modulo 26, then show why 10 has none.
  6. Trace 5^11 mod 13 and state the repeated-squaring invariant before and after an odd-exponent step.
  7. Solve 8x ≡ 4 (mod 12), proving the list complete; change b to 3 and prove no solution.

Keep your first attempt before consulting the key. Use actual failures for regression tests and corrected proofs. If your first attempt was correct, construct a deliberately faulty variant, label it as such, and explain why your check rejects it. No extra credit is awarded for page count.