Math & Number Theory Essentials

Start with the invariant and the integer range

You need integer division, remainders, loops, and binary representation. By the end, you should be able to explain why Euclid preserves the answer, fold an array into an exact GCD and a bounded LCM, reconstruct modular exponentiation from its invariant, and count primes with an exclusive upper bound.

Work through each state table before implementing its exercise. The checkpoint uses different numbers and asks you to diagnose boundary mistakes.

Euclid: replace a pair without changing its common divisors

For positive a and b, division gives a = q*b + r, where 0 <= r < b. Any divisor of both a and b divides r = a-q*b. Conversely, any divisor of b and r divides a = q*b+r. Therefore gcd(a,b) = gcd(b,a%b). The second argument strictly decreases until it is zero; gcd(a,0)=a.

Pair before a step	Remainder	Next pair
(84,30)	84 % 30 = 24	(30,24)
(30,24)	30 % 24 = 6	(24,6)
(24,6)	24 % 6 = 0	(6,0); answer 6

For an array, g is the GCD of exactly the processed prefix. Initialize it with the first value and replace it with gcd(g,value) for each later value. It can decrease: [12,18,25] produces GCD states 12,6,1.

LCM: divide first, then check before multiplying

For positive integers, lcm(a,b) = (a/gcd(a,b))*b. Common prime factors appear in both inputs; dividing by their GCD removes the duplicated contribution. LCM also folds over a prefix:

Processed values	GCD of prefix	LCM calculation	LCM of prefix
[6]	6	initialize	6
[6,10]	2	(6/2)*10	30
[6,10,15]	1	(30/15)*15	30

Use gcd(currentLCM,value) in the LCM calculation, not the running GCD of all array elements. Those quantities describe different pairs.

The exercise returns [gcd,lcm], with lcm=-1 when the mathematical LCM exceeds MAX = 9_223_372_036_854_775_807, the signed 64-bit maximum. This applies in both Go and Python. Input values are positive, so -1 is an unambiguous overflow result. GCD must still be exact.

Dividing first avoids an unnecessarily large intermediate but cannot make an unrepresentable result fit. For example, [1000000000,999999999,999999997] has LCM 999999996000000003000000000; the required output is [1,-1]. For a positive next value v, calculate q = lcm/gcd(lcm,v) and test:

if q > MAX / v using integer division:
    mark LCM as overflowed
else:
    nextLCM = q * v

Check before multiplication; a wrapped product cannot reliably tell you what the mathematical product was. Go permits signed integer overflow without a panic; see the Go integer-overflow specification. Python's larger integers do not change this exercise's shared output contract.

Every later LCM is a multiple of the previous positive LCM. Once overflowed, it stays overflowed: skip further LCM arithmetic, but continue the GCD fold. For [1000000000,999999998,999999996,3], overflow happens before the last value; that last value still changes the GCD from 2 to 1. Do not feed the -1 sentinel into the LCM formula.

With bounded machine arithmetic, the fold uses O(n log M) time for maximum input value M and O(1) extra space. You never need to construct the enormous mathematical LCM after detecting overflow.

Modular exponentiation: preserve the remaining product

The task permits nonnegative base and exponent and a positive modulus m. Represent every result in [0,m). Reduction preserves multiplication: (a*b) mod m = ((a mod m)*(b mod m)) mod m.

Keep result, current power x, and remaining exponent e. The invariant is:

result * x^e is congruent to originalBase^originalExponent modulo m

Initialize result=1 mod m, x=base mod m, e=exp. If e is odd, move one factor x into result; then square x and replace e by e//2. An even exponent needs only the square and halve steps.

Trace 5^13 mod 23. Each row records the complete state after a step:

Action	result	x	e
Initialize	1	5	13
Odd: multiply, square, halve	5	2	6
Even: square, halve	5	4	3
Odd: multiply, square, halve	20	16	1
Odd: multiply, square, halve	21	3	0

At e=0, the invariant leaves result=21 as the answer. There are O(log(exp+1)) steps and O(1) extra space. For exp=0, return 1 mod m immediately, including 0 for m=1. This exercise uses that convention for 0^0 too.

Here m <= 1_000_000_007, so two reduced factors multiply to at most 1_000_000_006^2 = 1_000_000_012_000_000_036, which fits signed 64-bit. Reduce the initial base before any square. This argument would not justify ordinary multiplication for an arbitrary 64-bit modulus.

Sieve: count primes strictly less than n

Allocate flags for indices 0..n-1. Zero and one are not prime. For each still-prime p with p*p < n, mark p*p, p*p+p, ... while the index is < n. A smaller composite multiple p*k, with 2 <= k < p, already has a smaller prime factor and was covered earlier. Starting at p*p avoids redundant work.

For n=12, the candidate set starts at {2,3,4,5,6,7,8,9,10,11}:

Prime processed	Multiples visited below 12	Remaining candidates
2	4,6,8,10	2,3,5,7,9,11
3	9	2,3,5,7,11

The answer is 5. For n=11, the answer is 4, because 11 is excluded. For n=0,1,2, return zero before accessing flags 0 or 1. The sieve uses O(n log log n) time and O(n) space; trial division separately for every candidate repeats work and does not meet the intended approach at n=5_000_000.

Complete the missing steps

Keep the worked examples above available for the first task. Then close them for the second task. Write an answer before opening the check.

After processing [12,18], the running GCD is 6 and LCM is 36. Append 8:

Decision	Given work	Your missing result
Update the GCD	gcd(6,8)	?
Remove duplicated LCM factors	gcd(36,8)=4, so q=36/4	?
Check representability	compare q with MAX/8	overflow or multiply?
Complete the prefix	return [newGCD,newLCM]	?

Check the completed fold after attempting it

The new GCD is 2, q is 9, the multiplication is representable, and the pair is [2,72]. Dividing 36 by the running GCD 2 would incorrectly produce 144. The LCM step needs the GCD of its own two operands, 36 and 8.

Now reconstruct both folds for [18,24,35] without the table. Separately, reconstruct the states for 3^7 mod 11 and predict whether moving the sieve's bound from 49 to 50 adds a prime. Explain each result before checking it.

Check the independent reconstruction

The GCD states are 18,6,1; LCM states are 18,72,2520. Power states (result,x,e) are (1,3,7) → (3,9,3) → (5,4,1) → (9,5,0). Both prime counts are 15: 49 enters the candidate interval when n becomes 50, but 49=7*7 is marked composite. The exclusive bound does not make a composite endpoint prime.

On a later visit, work a new array before reopening your implementation. A correct remembered output is weaker evidence than reconstructing the fold and its overflow boundary from the invariant.

Reconstruct, then check

1. Implement GCD and LCM. Try a repeated value, a large representable LCM, an overflow, and a value that changes GCD after overflow.
2. Implement modular exponentiation. Predict 7^0 mod 1 before running it; inspect why the initial reduction protects multiplication.
3. Implement prime counting. Compare n=11 and n=12 and explain why p*p is both the starting point and the outer stopping bound.

If you miss an overflow question, revisit the pre-multiplication check; if you miss a power trace, write the invariant above every row; if you miss a prime count, write the exact index interval before marking anything.