# 0.2: Definition

- Page ID
- 7447

For \(x,n\in Z\), we say that \(n\) **divides** \(x\) (or \(x\) **is a multiple of** \(n\)), and write \(n\mid x\), if there exists an integer \(k\) such that \(kn = x\).

We say that \(a\) and \(b\) are **congruent modulo** n, and write \(a\equiv_n b\), if \(n\mid (a − b)\). Equivalently, \(a\equiv_n b\) if and only if \(a\) % \(n = b\) % \(n\).

We write \(\mathbb{Z_n} \stackrel{\text{def}}{=}\{0,...,n-1\}\) to denote the set of **integers modulo** \(n\).

In other textbooks you may have seen “\(a\equiv_n b\)” written as “\(a\equiv b (\text{mod} \space n)\)”.

There is a subtle — and often confusing — distinction between the expressions “\(a \% n = b\)” and “\(a\equiv_n b\).” In the first expression, “\(a \% n\)” refers to an integer that is always between 0 and \(n − 1\), and the equals sign denotes equality over the integers. In the second expression, the “\(\equiv_n\)” symbol denotes congruence modulo \(n\), which is a weaker condition than equality over the integers. Note that \(a = b\) implies \(a\equiv_n b\), but not vice-versa.

## Example

\(99\equiv_{10}19\) because 10 divides 99 − 19 according to the definition. But \(99 \neq19\) % 10 because the right-hand side evaluates to the integer 19 \(\%\) 10 = 9, which is not the same integer as the left-hand side 99.

When adding, subtracting, and multiplying modulo n, it doesn’t affect the final result to reduce intermediate steps modulo n. That is, we have the following facts about modular arithmetic:

\[(a+b)\% n=[(a\% n)+(b\% n)]\% n;\nonumber\]

\[(a-b)\% n=[(a\% n)-(b\% n)]\% n;\nonumber\]

\[ab\% n=[(a\% n)(b\% n)]\% n;\nonumber\]

Division is not always possible in \(\mathbb{Z_n}\); we will discuss this fact later in the class.

## Strings

We write \({\{0,1\}}^n\) to denote the set of n-bit binary strings, and \({\{0,1\}}^{\ast}\) to denote the set of all (finite-length) binary strings. When \(x\) is a string of bits, we write \(|x|\) to denote the length (in bits) of that string, and we write \(\bar{x}\) to denote the result of flipping every bit in \(x\). When it’s clear from context that we’re talking about strings instead of numbers, we write \(0^n\) and \(1^n\) to denote strings of \(n\) zeroes and n ones, respectively.

When \(x\) and \(y\) are strings of the same length, we write \(x\oplus y\) to denote the bitwise exclusive-or (XOR) of the two strings. So, for example, \(0011\oplus 0101 = 0110\). The following facts about the XOR operation are frequently useful:

\[x\oplus x=0^{|x|}\space \space \space\space \space \space \text{XOR'ing a string with itself results in zeros}\nonumber\]

\[x\oplus 0^{|x|}=x \space \space \space\space \space \space \text{XOR'ing with zeros has no effect}\nonumber\]

\[x\oplus 1^{|x|}=\bar{x} \space \space \space \space \space \space\text{XOR'ing with ones flips every bit}\nonumber\]

\[x\oplus y=y\oplus x \space \space \space \space \space \space\text{XOR is symmetric}\nonumber\]

\[(x\oplus y)\oplus z=x\oplus (y\oplus z)\space \space\space \space \space \space \text{XOR is associative}\nonumber\]

As a corollary:

\[a=b\oplus c\Longleftrightarrow b=a\oplus c \Longleftrightarrow c=a\oplus b\nonumber\]

We use notation \(x‖y\) to denote the concatenation of two strings \(x\) and \(y\).

## Functions

Let \(X\) and \(Y\) be finite sets. A function \(? : X\rightarrow Y\) is:

**injective** (1-to-1) if it never maps twp different inputs to the same output. Formally: \(x\neq x'\Rightarrow f(x)\neq f(x')\).

**surjective** (onto) if every element in \(Y\) is a possible output of f. Formally: for all \(y\in Y\) there exists an \(x\in X\) with \(f(x)=y\).

**bijective** (1-to-1 correspondence) if f is both injective and surjective. If this is the case, we say that f is a bijection. Note that bijectivity implies that \(|X|=|Y|\).