Number Theory CST 292 KTU Honors IV Semester - Dr Binu V P

We will now consider the solutions of simultaneous congruences. In the 1st century AD, the Chinese mathematician Sun-Tsu considered problems like ‘find a number which leaves remainders 2,3,2 when divided by 3,5,7 respectively’. Equivalently, he wanted to find $x$ such that the congruences $$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod {5}, \quad x \equiv 2 \pmod {7}$$   are simultaneously true. Note that if $x_0$ is any solution, then so is $x_0 +(3 \times 5 \times 7)t$ for any integer $t$, so the solutions form a union of congruence classes mod (105). We shall show that in this particular case the solutions form a single congruence class, but in other cases we may find that there are several classes or none: as an example, the simultaneous congruences $$x \equiv 3 \pmod {9},\quad  x \equiv 2 \pmod {6}$$ have no solutions, for if $x \equiv 3 \pmod {9}$ then 3 divides $x$, whereas if $x \equiv 2\pmod {6}$ then 3 does not divide $x$. The difficulty here is that the moduli 9 and 6 have

Congruence Let $n$ be a positive integer, and let $a$ and $b$ be any integers. We say that $a$ is congruent to $b \pmod {n}$, or $a$ is a residue of $b \pmod{ n}$, written $$a \equiv b   \pmod {n}$$ If $a$ and $b$ leave the same remainder when divided by $n$.To be more precise, we use the division algorithm to put $a=qn+r$ with $0 \le r \lt n$, and $b=q'n+r'$ with  $0 \le r' \lt n$, and then we say that $a \equiv b \pmod {n}$  if and only if $r=r'$ Example: both 28 and 48 leave the same reminder when divided by 5. ie $48 \equiv 28 \pmod{5}$ We will use the notation $a \not \equiv b \pmod {n}$ to denote that $a$ and $b$ are not congruent $\pmod{n}$,that is, they leave different remainders when divided by $n$. Example:  $100\equiv 2 \pmod{7}$ $20 \not \equiv 3 \pmod{5}$    Theorem: $a \equiv b \pmod{m}$ if and only if $a=b+km$ for some integer $k$. Proof: suppose $a \equiv b \pmod{m}$, then $m |(a-b)$, so $a-b=km$ for some integer $k$, tht is $a= b+km$. Example: $23 \equ

Two theorems that play important roles in public-key cryptography are Fermat’s theorem and Euler’s theorem. Fermat’s Theorem ( Fermat's Little Theorem) Fermat’s theorem states the following: If $p$ is prime and $a$ is a positive integer not divisible by $p$, then  $$a^{p-1} \equiv 1 \pmod{p}$$ Proof: Consider the set of positive integers less than $p:\{1,2,\ldots,p-1\}$ and multiply each element by $a$, modulo $p$, to get the set $X=\{a \pmod{p},2a \pmod{p},\ldots,(p-1)a \pmod{p}\}$ None of the elements of $X$ is equal to zero because $p$ does not divide $a$. Furthermore, no two of the integers in $X$ are equal.To see this,assume that $ja \equiv ka \pmod{p}$, where $i \le j \lt k \le (p-1)$. Because $a$ is relatively prime to $p$ , we can eliminate $a$ from both sides of the equation resulting in $j \equiv k \pmod{p}$ .This last equality is impossible, because $j$ and $k$ are both  positive integers less than $p$.Therefore, we know that the $(p-1)$ elements of  $X$ are  all posit