Number Theory

The floor operator, denoted \(\left \lfloor{x}\right \rfloor\), tells us the greatest integer \(\leq x\).

The ceiling operator, denoted \(\left \lceil{x}\right \rceil\), tells us the smallest integer \(\geq x\).

(Basically, they’re just fancy ways of saying “round down” and “round up”)

Example

• \(\left \lfloor{7.5}\right \rfloor = 7\)
  
• \(\left \lceil{7.5}\right \rceil = 8\)

\(x-1 < \left \lfloor{x}\right \rfloor \leq x\)

• Why?
• By definition, we know \(\left \lfloor{x}\right \rfloor \leq x\)
• We know \(x-1 < \left \lfloor{x}\right \rfloor\) because:
  • We can write \(x\) as \(x = y + d\) where \(y\) is an integer and \(d\) is a decimal. (E.g. \(7.5 = 7 + .5\))
  • We know \(\left \lfloor{x}\right \rfloor = y\) and that \(d\) is some real number such that \(0 \leq d < 1\).
  • We know \(d < 1\), so \(d-1\) is negative, therefore \(y + d - 1 < y\).
  • So \(x - 1 = y + d - 1 < y = \left \lfloor{x}\right \rfloor\)

\(x \leq \left \lceil{x}\right \rceil < x + 1\)

• (You can prove this similarly to the way we proved the floor property!)

We usually represent numbers in base ten

• In general, a number in the form of digits \(d_k d_{k-1} \ldots d_1 d_0\) can be represented as \[\sum_{i\in[0,k]}d_i t^i = d_kt^k + d_{k-1}t^{k-1}+ \ldots + d_1t^1 + d_0t^0\] where \(t\) is the base
• All digits \(d_i\) are in the range \([0,t-1]\)

Example

• Let’s go back to representing the number \(10,475\) in base \(10\)
• So the digits are \(d_4 = 1\), \(d_3 = 0\), \(d_2 = 4\), \(d_1 = 7\), \(d_0 = 5\) and the base is \(t = 10\)
• Which gives us what we got before: \(10,475 = 1 \cdot 10^4 + 0 \cdot 10^3 + 4 \cdot 10^2 + 7 \cdot 10^1 + 5 \cdot 10^0\)
• Also note that all digits are between \(0\) and \(9\).

• Often in computer science, we represent numbers in base \(2\). This is also called “binary” representation.
• Since our base \(t = 2\), then our digits are in the range \([0,1]\). So basically, we are just looking at strings of \(0\)s and \(1\)s.
  (Often we call \(0\)s and \(1\)s “bits”. \(8\) bits is a byte.)

If I want to express \(x\) in binary, how long will it be?

(In other words, how many bits will it take?)

• Think about the procedure we just did for converting a number to binary. We find the highest power of \(2\) that is less than or equal to \(x\): \(k = \left \lfloor{\log_2(x)}\right \rfloor\)
• We know this means that our string of bits will be of length \(k\).
• This can be generalized for any base \(b\): The length of any number \(x\) in base \(b\) is \(\left \lfloor{\log_b(x)}\right \rfloor\)

For positive Integers, \(x \bmod y\) is the remainder of \(x/y\).

More generally, \(x \bmod y = x - \left \lfloor{x/y}\right \rfloor \cdot y\).

Examples

• \(5 \bmod 2 = 1\)
• \(4 \bmod 2 = 0\)
• \(-1 \bmod 2 = 1\)
• Note that the value of \(x \bmod y\) is between \(0\) and \(y-1\)!

Another way we can express mods is via congruency.

\(x \equiv z \pmod y\) reads as “\(x\) is congruent to \(z\) mod \(y\)”.

What this means is that \(x \bmod y = z \bmod y\).

Example

• \(4 \bmod 2 = 0\) and \(6 \bmod 2 = 0\), so \(4 \equiv 6 \pmod 2\).

The greatest common divisor of two integers \(x\) and \(y\), denoted \(GCD(x,y)\) is the largest positive integer that divides both \(x\) and \(y\).

Example

• \(GCD(8,12) = 4\)
• \(GCD(3,6) = 3\)
• \(GCD(4,7) = 1\)

If \(GCD(x,y) = 1\), then \(x\) and \(y\) are relatively prime (also called coprime).