STEP-BY-STEP LESSON · §4.10
Application: Algorithms
Track variable changes in a step-by-step algorithm.
Before you begin
Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem
For integer n and positive integer d there are unique integers q,r with n=dq+r and 0≤r<d.
n=dq+r; 0≤r<d
Symbols
- :=
- assign a value
- mod
- remainder
- gcd(a,b)
- greatest common divisor of a and b
Definitions and notation for this topic
Greatest common divisor
gcd(a,b)
The greatest positive integer dividing both given integers, which are not both zero.
The number 6 divides both; no larger positive integer does.
Separate glossary example
gcd(12,18)=6
Modulo: remainder value
a mod m
For integer a and positive integer m, a mod m is the unique integer r with a=mq+r and 0≤r<m for some integer q.
This produces one number. The statement a≡b (mod m) instead says their remainders agree. Some programming languages use a different convention for a negative dividend.
Separate glossary example
−17 mod 5=3 because −17=5(−4)+3.
Assignment and program state
x:=e
Evaluate e using the current variable values, then replace the value stored in x. A state records the current values of the algorithm’s variables.
The right-hand x is read before the replacement. Assignment is an action; x=4 is a statement about a state, and 4∈A is set membership.
Separate glossary example
Starting with x=3, the instruction x:=x+1 changes the state to x=4.
Step by step
Step 1 / 6
Equality and assignment
Assignment evaluates the right side using current values and stores the result in the left variable. It changes the state.
x:=x+1
The old x is used on the right before replacement.
Worked example
Original trainer example. Find gcd(18,12) using Euclid’s algorithm.
- 18=12·1+6: replace (18,12) with (12,6).
- 12=6·2+0: replace the pair with (6,0) and stop.
- The last nonzero value is 6, so the gcd is 6.
Optional self-check
Starting with x=4, what is x after x:=x+1?
Show answer
First compute 4+1=5, then store x=5.