GCD and prime basics

Understand the idea

Euclid repeatedly replaces (a,b) with (b,a%b). Common divisors are unchanged and the nonnegative remainder shrinks. Primality trial division checks divisors only through the square root because factors pair. For counting many primes below n, use a sieve instead of testing every candidate independently. Begin with all integers from 2 as possible primes. For each unmarked p with p*p<n, mark p*p,p*p+p,... as composite. Smaller multiples already have a smaller prime factor. Remaining unmarked positions are prime. This uses O(n) storage and O(n log log n) marking work, trading memory for repeated primality checks.

Work through an example

48,18→18,12→12,6→6,0 returns 6. To test 29, check possible divisors through 5; none divide it.

Time and space complexity

O(log min(a,b)) remainder steps for positive inputs; trial division O(√n) candidates.

Why it works

gcd(a,b)=gcd(b,a%b); the remainder decreases toward zero.

Common mistakes

• 1 is not prime.
• For large n, d*d can overflow in fixed-width arithmetic.

Chapter lab · Python implementation

Arithmetic assumptions affect algorithm correctness. The lab uses Euclid for GCD, modular repeated squaring, and a square-matrix rotation. Python integers avoid fixed-width overflow but grow in storage and arithmetic cost. Treat coordinate conventions and modular inverses explicitly rather than relying on memorized formulas.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def gcd(a,b):
    a,b=abs(a),abs(b)
    while b: a,b=b,a%b
    return a

def mod_power(base,exponent,modulus):
    if exponent<0 or modulus<1: raise ValueError('invalid exponent/modulus')
    result=1%modulus; base%=modulus
    while exponent:
        if exponent&1: result=result*base%modulus
        base=base*base%modulus; exponent//=2
    return result

def rotate(matrix):
    n=len(matrix)
    if any(len(row)!=n for row in matrix): raise ValueError('square required')
    for r in range(n):
        for c in range(r+1,n):
            matrix[r][c],matrix[c][r]=matrix[c][r],matrix[r][c]
    for row in matrix: row.reverse()

def count_primes(limit):
    if limit<2: return 0
    prime=bytearray([1])*limit
    prime[0]=prime[1]=0
    p=2
    while p*p<limit:
        if prime[p]:
            for multiple in range(p*p,limit,p):
                prime[multiple]=0
        p+=1
    return sum(prime)

def digit_power(base,digits,modulus):
    if modulus<1 or any(not 0<=d<=9 for d in digits):
        raise ValueError('positive modulus and decimal digits required')
    result=1%modulus
    for digit in digits:
        result=mod_power(result,10,modulus)*mod_power(base,digit,modulus)%modulus
    return result

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert gcd(48,18)==6 and gcd(-8,0)==8 and gcd(0,0)==0
assert mod_power(3,5,7)==pow(3,5,7)==5
assert mod_power(9,0,1)==0
a=[[1,2],[3,4]]; rotate(a); assert a==[[3,1],[4,2]]
assert all(mod_power(5,e,13)==pow(5,e,13) for e in range(30))
assert count_primes(10)==4 and count_primes(0)==0
assert count_primes(2)==0 and count_primes(100)==25
assert digit_power(2,[1,0],1337)==pow(2,10,1337)
assert digit_power(3,[2,0,1],1337)==pow(3,201,1337)