Skip to main content

Answer Key and Calibration

Practice​

  1. -23 = -4*7 + 5; 23 = 3*7 + 2. Uniqueness follows because the difference of two legal remainders cannot be a nonzero multiple of 7.
  2. gcd=6, with 6 = -84 + 3*30. For inputs -84,30 choose coefficients 1,3.
  3. A divisor of both a,b divides a-qb; a divisor of b,a-qb also divides a. Positive remainders strictly decrease.
  4. 90 = 2*3^2*5, 126 = 2*3^2*7; gcd=18. Factoring is unnecessary overhead for gcd.
  5. Inverse 19, since 11*19 - 26*8 = 1; gcd(10,26)=2, so 10 has no inverse.
  6. Squared residues for 5 modulo 13: 5,12,1,1. Since 11=8+2+1, result is 8. Maintain result times base to the remaining power congruent to the original power.
  7. [2,5,8,11]; reduce to x=2 modulo 3, then lift. Target 3 fails because gcd(8,12)=4 does not divide it.

Quiz​

  1. The remainder must be nonnegative and smaller than 7.
  2. Also establish that the returned value divides both inputs and is nonnegative. For example, 2*1+3*1=5 is an identity but 5 is not their gcd.
  3. Primality requires an integer greater than 1; excluding the square-root endpoint misses squares such as 49.
  4. gcd(a,m)=1. Modulo 6, 2*1 and 2*4 are congruent, but 1 and 4 are not.
  5. See the invariant in Lesson 5; exponent zero returns 1 % m, hence zero for m=1 under this API.
  6. Let g=gcd(a,m). Solvable exactly when g divides b; then there are g distinct representatives in [0,m).

Fresh defense calibration​

gcd(-105,66)=3, with coefficients (5,8): -105*5 + 66*8 = 3. Other valid coefficients are acceptable. For 9x ≡ 6 (mod 15), reduce to 3x ≡ 2 (mod 5), yielding [4,9,14]. Target 7 is impossible because 3 does not divide 7. 4^9 mod 19 = 1; squared residues are 4,16,9,5, and 5*4 reduces to 1.

Correct outputs alone do not pass the proof, complexity or transfer gates. Use the separate lab reference only after an attempt, and retain a note explaining every borrowed repair.

Entry-check calibration​

Attempt these before the modular-arithmetic lessons: write 23 = 3*7 + 2; trace a loop that starts at 3 and decrements until zero; explain why three successful examples do not prove a claim about every integer; write a function returning [x, x+1] and distinguish its return from printing. These check prior algebra, termination, quantifiers and functions. If weak, use the index's Semester 00/proofs repair route and repeat with new inputs. This calibration is inside the existing 25–35-hour route; it adds no extra gate or project.