Day 5 — Division algorithm, mod, floor & ceiling

Day 5 — Division algorithm, mod, floor & ceiling

Stage I · concept day
Goal: State and use the division algorithm with unique \(q,r\); define floor and ceiling with identities; document % vs mathematical mod for negatives; introduce residue classes and congruence.

Why this matters

Integer division with remainder is how clocks, hash tables, circular buffers, pagination, and calendar arithmetic work. Floor and ceiling appear in complexity, block counts, and “how many pages for \(n\) items.” Negative operands are the #1 source of language-dependent bugs.

Theory

Division algorithm

Theorem (division algorithm). Let \(a\in\mathbb{Z}\) (dividend) and \(d\in\mathbb{Z}\) with \(d\neq 0\) (divisor). There exist unique integers \(q\) (quotient) and \(r\) (remainder) such that

\[a = dq + r\qquad\text{and}\qquad 0\le r < |d|.\]

(Common statement takes \(d>0\) and \(0\le r<d\).)

Existence idea (\(d>0\)). Consider the set of all integers of the form \(a-dq\) for \(q\in\mathbb{Z}\). Choose \(q\) so that \(r=a-dq\) is nonnegative and minimal among nonnegative candidates (or: take \(q=\lfloor a/d\rfloor\)). Then \(0\le r<d\): if \(r\ge d\), then \(a-d(q+1)=r-d\ge 0\) is a smaller nonnegative remainder, contradiction.

Uniqueness. Suppose \(a=dq_1+r_1=dq_2+r_2\) with \(0\le r_i<d\) (assume \(d>0\)). Then \(d(q_1-q_2)=r_2-r_1\), so \(d\) divides \(r_2-r_1\). But \(|r_2-r_1|<d\), so \(r_2-r_1=0\), hence \(r_1=r_2\) and \(q_1=q_2\). \(\square\)

Notation: mod and congruence

We write \[a\bmod d = r\] for the remainder in the division algorithm (with the convention \(0\le r<|d|\) when we fix mathematical remainder).

Congruence: \(a\equiv b\pmod{d}\) means \(d\mid (a-b)\), equivalently \(a\) and \(b\) leave the same remainder on division by \(d\) (for \(d>0\)).

Floor and ceiling

For real \(x\):

• \(\lfloor x\rfloor\) = greatest integer \(\le x\) (floor)
  
• \(\lceil x\rceil\) = least integer \(\ge x\) (ceiling)

Examples: \(\lfloor 3.2\rfloor=3\), \(\lceil 3.2\rceil=4\), \(\lfloor -3.2\rfloor=-4\), \(\lceil -3.2\rceil=-3\).

Identities (selected):

1. \(\lfloor x\rfloor \le x < \lfloor x\rfloor+1\)
   
2. \(\lceil x\rceil-1 < x \le \lceil x\rceil\)
   
3. \(\lfloor x\rfloor = n \Leftrightarrow n\le x<n+1\) for \(n\in\mathbb{Z}\)
   
4. For \(n\in\mathbb{Z}\), \(\lfloor n\rfloor=n=\lceil n\rceil\)
   
5. \(\lceil x\rceil = -\lfloor -x\rfloor\)
   
6. For integer \(n\) and real \(x\): \(\lfloor n+x\rfloor=n+\lfloor x\rfloor\)
   
7. For positive integer \(m\) and integer \(a\):
   \(\bigl\lfloor\frac{a}{m}\bigr\rfloor\) is the quotient when \(a\ge 0\) in \(a=mq+r\) with \(0\le r<m\)

Block counts: number of groups of size \(m\) needed for \(n\) items is \(\lceil n/m\rceil\) (for \(m>0\)).

Language % vs mathematical mod (negatives)

Critical: programming languages disagree on the sign of a % d when \(a\) or \(d\) is negative.

Convention	Rule of thumb	Example \(-7\) div \(3\)
Mathematical / Euclidean	Remainder \(r\) with \(0\le r<|d|\)	\(-7=3\cdot(-3)+2\), \(r=2\)
Truncated toward zero (C/C++/Java for /)	Quotient truncates toward \(0\); remainder has sign of dividend	\(-7/3\to -2\), remainder \(-7-3(-2)=-1\)
Floored division (Python //)	Quotient \(=\lfloor a/d\rfloor\); remainder \(a-d q\)	\(-7//3=-3\), -7%3=2

Document both. In this book, mathematical \(\mathrm{mod}\) means the division-algorithm remainder \(0\le r<|d|\) (or \(0\le r<d\) if \(d>0\)). When discussing code, name the language convention.

Python: (-7) % 3 == 2 (floored).
C99 / Java: (-7) % 3 == -1 with toward-zero /.

Residue classes

For modulus \(m>0\), the residue class of \(a\) is \[[a]_m = \{ a+km : k\in\mathbb{Z}\}=\{\ldots,a-2m,a-m,a,a+m,a+2m,\ldots\}.\]

There are exactly \(m\) distinct classes: \([0],[1],\ldots,[m-1]\).
\(\mathbb{Z}/m\mathbb{Z}\) is the set of these classes (modular arithmetic system).
\(a\equiv b\pmod m\) iff \([a]_m=[b]_m\).

Arithmetic on residues (preview): \([a]+[b]=[a+b]\), \([a][b]=[ab]\) is well-defined.

Relating gcd and linear combinations (preview)

Remainders in the Euclidean algorithm are integer linear combinations of \(a\) and \(b\); eventually \(\gcd(a,b)=ax+by\) (Bézout). Full use later in modular inverses.

Worked examples

Example 1 — Positive division

\(a=100\), \(d=7\): \(100=7\cdot 14+2\), so \(q=14\), \(r=2\). \(100\bmod 7=2\). \(100\equiv 2\pmod 7\).

Example 2 — Negative dividend (math)

\(a=-100\), \(d=7\): find \(q\) so \(0\le r<7\). \(-100=7q+r\Rightarrow\) try \(q=-15\): \(7(-15)=-105\), \(r=5\). Check \(-100=-105+5\). So \(-100\bmod 7=5\), and \(-100\equiv 5\pmod 7\).

Example 3 — Truncated vs floored

\(-100/7\) toward zero: quotient \(-14\), remainder \(-100-7(-14)=-100+98=-2\).
Floored: quotient \(\lfloor -100/7\rfloor=\lfloor -14.285\ldots\rfloor=-15\), remainder \(5\) as above.

Example 4 — Floor/ceiling negatives

\(\lfloor -7/3\rfloor=\lfloor -2.333\rfloor=-3\).
\(\lceil -7/3\rceil=\lceil -2.333\rceil=-2\).
\(\lceil 7/3\rceil=3\), \(\lfloor 7/3\rfloor=2\).

Example 5 — Identity \(\lceil x\rceil=-\lfloor -x\rfloor\)

\(x=2.3\): \(\lceil 2.3\rceil=3\), \(-\lfloor -2.3\rfloor=-( -3)=3\).
\(x=-2.3\): \(\lceil -2.3\rceil=-2\), \(-\lfloor 2.3\rfloor=-2\).

Example 6 — Pages / blocks

\(n=50\) items, page size \(m=8\): \(\lceil 50/8\rceil=\lceil 6.25\rceil=7\) pages. Last page has \(50-6\cdot 8=2\) items.

Example 7 — Congruence arithmetic

\(17\equiv 5\pmod{12}\), \(20\equiv 8\pmod{12}\), sum \(37\equiv 1\pmod{12}\), and \(5+8=13\equiv 1\pmod{12}\).

Example 8 — Residue class

\([3]_5=\{\ldots,-7,-2,3,8,13,\ldots\}\). Same as \([-2]_5\).

Example 9 — Clock

Hours: \(15\bmod 12=3\) o’clock form. \(15\equiv 3\pmod{12}\).

Example 10 — Even/odd via mod

\(n\) even \(\Leftrightarrow n\equiv 0\pmod 2\); odd \(\Leftrightarrow n\equiv 1\pmod 2\).

Example 11 — Floor of sum

\(\lfloor 3+2.7\rfloor=5=\lfloor 3\rfloor+\lfloor 2.7\rfloor\).
But \(\lfloor 2.7+2.7\rfloor=\lfloor 5.4\rfloor=5\neq 2+2=4\): floor does not always distribute over addition of non-integers.

Example 12 — Quotient formula

For \(a=20\), \(m=6\): \(\lfloor 20/6\rfloor=3\), remainder \(2\), \(20=6\cdot 3+2\).

Example 13 — Negative divisor (careful)

\(a=20\), \(d=-6\). Require \(0\le r<6\) (\(|d|=6\)). \(20=(-6)q+r\). Try \(q=-3\): \((-6)(-3)=18\), \(r=2\). So \(20=(-6)(-3)+2\).

Example 14 — Python vs C mental model

Predict (-7)%3: Python \(2\); C toward-zero remainder \(-1\). Always check language docs for signed %.

Exercises

Easy

1. Divide \(85\) by \(9\): find \(q,r\) with \(0\le r<9\).
2. Compute \(85\bmod 9\) and \(9\bmod 85\).
3. Evaluate \(\lfloor 9.99\rfloor\), \(\lceil 9.01\rceil\), \(\lfloor -9.01\rfloor\), \(\lceil -9.99\rceil\).
4. How many boxes of capacity \(12\) are needed for \(100\) items?
5. Write \([7]_{5}\) as equal to \([r]_5\) with \(0\le r<5\).

Medium

6. Find math-mod remainders: \((-85)\bmod 9\) and \((-85)\bmod 10\).
7. Prove uniqueness in the division algorithm for \(d>0\).
8. Show \(a\equiv b\pmod m\) iff \(a\) and \(b\) have the same remainder on division by \(m\) (\(m>0\)).
9. Verify \(\lceil x\rceil=-\lfloor -x\rfloor\) for \(x=4\), \(x=-4\), \(x=4.2\), \(x=-4.2\).
10. Compute \(\lfloor n/2\rfloor\) for \(n=0,1,2,3,10,11\) (integer half).
11. If today is day index \(2\) (Wednesday) and \(m=7\), what day index is \(100\) days later?
12. Express \(a=dq+r\) for \(a=-17\), \(d=5\) (math remainder).
13. Give a counterexample: \(\lfloor x+y\rfloor\neq\lfloor x\rfloor+\lfloor y\rfloor\).

Hard / proof

14. Prove existence of \(q,r\) for \(a\in\mathbb{Z}\), \(d>0\) using \(q=\lfloor a/d\rfloor\).
15. Prove: for integer \(n\) and real \(x\), \(\lfloor n+x\rfloor=n+\lfloor x\rfloor\).
16. Prove: number of multiples of \(m>0\) in \(\{1,2,\ldots,N\}\) is \(\lfloor N/m\rfloor\).
17. Show there are exactly \(m\) distinct residue classes mod \(m\).
18. Relate Euclidean algorithm step \(a=bq+r\) to \(\gcd(a,b)=\gcd(b,r)\).
19. For \(m>0\), prove \(a\equiv b\pmod m\) and \(c\equiv d\pmod m\) imply \(a+c\equiv b+d\) and \(ac\equiv bd\pmod m\).
20. Explain with one table: truncated vs floored division for all sign combinations of \(\pm 7\) and \(\pm 3\) (quotient and remainder).

Challenge / CS-flavored

21. Circular buffer length \(m=8\), head index \(h=6\), advance \(k=5\) steps: new index \((h+k)\bmod m\).
22. Pagination: items \(0..n-1\), page size \(p\). Which page is index \(i\)? How many items on the last page?
23. Hash: \(h(k)=k\bmod m\) with \(m=10\). Collisions among keys \(17,27,37\)?
24. Why might if (n % 2 == 1) miss negative odds in C? What test is safer for “odd”?
25. Prove \(\lfloor x\rfloor \le\lceil x\rceil\) always, and equality iff \(x\in\mathbb{Z}\).

Congruence arithmetic laws (full)

For fixed \(m>0\):

1. \(a\equiv a\pmod m\)
   
2. \(a\equiv b\Rightarrow b\equiv a\)
   
3. \(a\equiv b\) and \(b\equiv c\Rightarrow a\equiv c\)
   
4. \(a\equiv b\) and \(c\equiv d\Rightarrow a+c\equiv b+d\) and \(ac\equiv bd\pmod m\)
   
5. \(a\equiv b\Rightarrow ka\equiv kb\pmod m\) for any integer \(k\)
   
6. Cancellation caution: \(ka\equiv kb\pmod m\) and \(\gcd(k,m)=1\) \(\Rightarrow\) \(a\equiv b\pmod m\). If \(\gcd(k,m)>1\), cancellation may fail (e.g. \(2\cdot 1\equiv 2\cdot 4\pmod 6\) but \(1\not\equiv 4\pmod 6\)).

Floor identities (catalog)

For real \(x,y\) and integer \(n\):

• \(\lfloor x\rfloor+\lfloor y\rfloor \le \lfloor x+y\rfloor \le \lfloor x\rfloor+\lfloor y\rfloor+1\)
  
• \(\bigl\lfloor\frac{\lfloor x\rfloor}{n}\bigr\rfloor=\bigl\lfloor\frac{x}{n}\bigr\rfloor\) for integer \(n>0\)
  
• \(\lceil n/m\rceil=\bigl\lfloor\frac{n+m-1}{m}\bigr\rfloor\) for integers \(n\ge 0\), \(m>0\) (useful packing identity)

Division algorithm for negative divisors

Require \(0\le r<|d|\) always. Then \(q\) is uniquely determined. Example: \(a=17\), \(d=-5\): \(17=(-5)(-3)+2\) because \(15+2=17\) and \(0\le 2<5\).

Modular “wrap” pictures

Clock: hours mod \(12\). Array ring buffer: indices mod capacity. Hash table: key % m with nonnegative keys first—signed keys need normalization to \([0,m)\).

Extra exercises

26. Prove \(\lceil n/m\rceil=\bigl\lfloor(n+m-1)/m\bigr\rfloor\) for integers \(n\ge 0\), \(m>0\).
    
27. Show \(a\equiv b\pmod m\Rightarrow a^k\equiv b^k\pmod m\) by induction on \(k\).
    
28. Find all \(x\) with \(0\le x<15\) and \(x\equiv 7\pmod 5\).
    
29. Compute \(\lfloor\sqrt{50}\rfloor\) and \(\lceil\sqrt{50}\rceil\) without a decimal approx beyond bounds \(7^2=49\), \(8^2=64\).
    
30. Language table: for \(a=-20\), \(d=6\), write math remainder, Python-style floored remainder, and toward-zero remainder.

CS connection

• Array strides and tiles: \(\lceil n/B\rceil\) blocks.
  
• Hashing: \(k\bmod m\) buckets.
  
• Time: Unix time mod \(86400\) for time-of-day (careful with time zones).
  
• Signed remainder bugs: security and correctness issues when assuming \(r\ge 0\).
  
• Complexity: loops with \(\lfloor n/2\rfloor\) iterations; master theorem floors later.

Common pitfalls

Pitfall	What to do instead
Assuming % always \(\ge 0\)	Check language; prefer math remainder for proofs
\(\lfloor -3.2\rfloor=-3\)	Floor goes down: \(-4\)
Confusing \(\mathrm{mod}\) with “modulo operation on reals”	Integer remainder / congruence
Forgetting uniqueness needs range of \(r\)	\(0\le r<|d|\) is essential
\(\lfloor x+y\rfloor=\lfloor x\rfloor+\lfloor y\rfloor\) always	False for non-integers
Residue class equals one number	Class is an infinite set; pick canonical \(0..m-1\)

Fully worked extra examples

E15 — Congruence chain.
\(17\equiv 2\pmod{5}\), \(23\equiv 3\pmod{5}\), so \(17\cdot 23\equiv 2\cdot 3=6\equiv 1\pmod{5}\). Check \(391/5\): \(5\cdot 78=390\), remainder \(1\).

E16 — Floor identity use.
Number of pages for \(n=250\), \(m=40\): \(\lceil 250/40\rceil=\lceil 6.25\rceil=7=\bigl\lfloor(250+39)/40\bigr\rfloor=\lfloor 289/40\rfloor=7\).

E17 — Negative divisor.
\(a=-30\), \(d=-7\), require \(0\le r<7\). Try \(q=5\): \((-7)(5)=-35\), \(r=5\), and \(-30=-35+5\). Yes.

E18 — Residue class equality.
\([7]_{5}=[2]_{5}=[-3]_{5}\) because differences multiples of \(5\).

End-of-day synthesis problems

S1. For \(a=-100\) and \(d=9\), find math \(q,r\) with \(0\le r<9\). Compare to toward-zero quotient/remainder.

S2. Prove uniqueness of \(q,r\) in the division algorithm for \(d>0\).

S3. Evaluate \(\lfloor -20/3\rfloor\), \(\lceil -20/3\rceil\), and show \(\lceil x\rceil=-\lfloor -x\rfloor\) for \(x=-20/3\).

S4. How many multiples of \(7\) lie in \(\{1,2,\ldots,100\}\)? Use floor.

S5. Prove \(a\equiv b\pmod m\Rightarrow a+c\equiv b+c\pmod m\).

S6. Circular buffer length \(16\), index \(14\), advance \(5\): new index.

S7. List canonical residues of \(-3,-2,\ldots,6\) mod \(5\).

S8. Identity: verify \(\lceil 100/12\rceil=\bigl\lfloor(100+12-1)/12\bigr\rfloor\).

Checkpoint

• State division algorithm with uniqueness
  
• Compute \(q,r\) for positive and negative dividends (math convention)
  
• Define floor/ceiling; evaluate on negatives
  
• Use \(\lceil n/m\rceil\) for packing counts
  
• Explain at least two signed-division conventions
  
• Define \(a\equiv b\pmod m\) and residue class \([a]_m\)
  
• Complete S1–S2 as exam-style writeups

Write two takeaways in your own words.

Deep dive — division algorithm, floor, congruence

D1 — Existence via floor (positive divisor).
For \(a\in\mathbb{Z}\), \(d>0\), set \(q=\lfloor a/d\rfloor\) and \(r=a-dq\). By definition of floor, \(q\le a/d<q+1\), so \(0\le a-dq<d\), i.e. \(0\le r<d\). Uniqueness was already proved by difference bound.

D2 — Full sign table (mental model).
For \(a=\pm 17\), \(d=\pm 5\), insist on mathematical remainder \(0\le r<|d|=5\).
\(17=5\cdot 3+2\); \(17=(-5)\cdot(-3)+2\);
\(-17=5\cdot(-4)+3\) because \(5(-4)=-20\), \(r=3\);
\(-17=(-5)\cdot 4+3\) because \((-5)(4)=-20\), \(r=3\).
Same \(r\) depends on \(|d|\) range, not the sign of \(d\) alone, under this convention.

D3 — Congruence product and failed cancellation.
\(14\equiv 8\pmod 6\) (both rem \(2\)). Also \(2\cdot 4\equiv 2\cdot 1\pmod 6\) but \(4\not\equiv 1\pmod 6\) because \(\gcd(2,6)=2\neq 1\).

D4 — Packing identity practice.
Items \(n=250\), page size \(m=12\): \(\lceil 250/12\rceil=\lceil 20.833\rceil=21\).
Check \(\bigl\lfloor(250+12-1)/12\bigr\rfloor=\lfloor 261/12\rfloor=\lfloor 21.75\rfloor=21\).
Last page size: \(250-20\cdot 12=10\).

D5 — Residue arithmetic clock.
Day index \(0\)=Sun,…, \(6\)=Sat. If today is \(4\) (Thu) and we add \(100\) days: \((4+100)\bmod 7=104\bmod 7=6\) (Sat), since \(104=14\cdot 7+6\).

D6 — Floor inequality sandwich.
Always \(\lfloor x\rfloor+\lfloor y\rfloor\le\lfloor x+y\rfloor\le\lfloor x\rfloor+\lfloor y\rfloor+1\).
Example: \(x=y=1.6\): left \(1+1=2\), middle \(\lfloor 3.2\rfloor=3\), right \(3\). Equality can hit either side depending on fractional parts.

Extra practice set

31. Find math \(q,r\) for \(a=-200\), \(d=13\).
    
32. Prove: number of multiples of \(m>0\) among \(1..N\) is \(\lfloor N/m\rfloor\).
    
33. Show \(a\equiv b\pmod m\) and \(c\equiv d\pmod m\) \(\Rightarrow\) \(ac\equiv bd\pmod m\).
    
34. Circular buffer capacity \(32\), index \(29\), step \(+7\): new index.
    
35. Verify \(\lceil x\rceil=-\lfloor -x\rfloor\) for \(x=\pm 7.1\) and \(x=\pm 7\).

Tomorrow

Day 6 — Positional bases. Place-value polynomials, convert among bases \(2\)–\(16\), hex↔︎binary via nibbles, digit validity, Horner’s method.