Number theory: prove the step, bound the value

• Euclid preserves common divisors.
• LCM needs a representable result or an explicit overflow outcome.
• Binary exponentiation preserves a product modulo m.
• The sieve counts primes strictly below n.

Euclid's remainder invariant

a=q*b+r: divisors of (a,b) equal divisors of (b,r).

(84,30) → (30,24) → (24,6) → (6,0)

The positive second argument decreases; return 6.

Fold GCD and LCM separately

For [6,10,15]:

LCM uses gcd(currentLCM,value), not the prefix GCD.

Overflow is part of the result contract

• MAX=9_223_372_036_854_775_807.
• Divide: q=currentLCM/gcd(currentLCM,v).
• Check q > MAX/v with integer division before multiplying.
• If true, keep LCM as -1; continue computing exact GCD.
• Positive-input LCM cannot shrink back into range.

Binary exponentiation

Invariant: result*x^e ≡ originalBase^originalExponent (mod m).

For 5^13 mod 23, states (result,x,e) are:

(1,5,13) → (5,2,6) → (5,4,3) → (20,16,1) → (21,3,0).

Odd: multiply result. Every step: square x and halve e.

Boundary and arithmetic checks

• Initialize result=1 mod m, so exponent zero with m=1 returns 0.
• Reduce the initial base before squaring.
• Here m <= 1_000_000_007; reduced products fit signed 64-bit.
• A larger modulus requires a new multiplication-range argument.

Sieve with an exclusive upper bound

For n=12, allocate indices 0..11.

• 0 and 1 are not prime.
• p=2 marks 4,6,8,10; p=3 marks 9.
• Remaining: 2,3,5,7,11 → 5 primes.
• n=11 instead excludes 11 and returns 4.
• Start at p²; continue only while p²<n.

Explain before submitting

• Why does Euclid preserve the GCD?
• Why must GCD continue after LCM overflows?
• Why does halving the exponent preserve the modular product?
• Which index is excluded from the prime count?