1. Let $n$ be a fixed positive number. Two integers $a$ and $b$ are said to be congruent modulo $n$, symbolized by
$a\equiv b \pmod{n}$ if $n$ divides the difference $a-b$., i.e., provided that $a-b = kn$ for some integer $k$.
- For ex. $23\equiv 3 \pmod{5}$, $19\equiv 3 \pmod{4}$, $12\equiv 5 \pmod{7}$, $5\equiv 5 \pmod{3}$,
2. For arbitrary integers $a$ and $b$,
$a\equiv b \pmod{n}$ iff $a$ and $b$ leave the same non negative remainder when divided by $n$
3. Let $n>1$ be fixed and $a, b, c, d$ be arbitrary integers. Then the following properties hold:
Ex.,
$7\equiv 7 \pmod{3}$
$7-7 = 0$ is a multiple of $3$. Hence $3$ divides $0$
- If $a\equiv b \pmod{n}$, then $b\equiv a \pmod{n}$
Ex.,
$17\equiv 3 \pmod{7}$ This congruence is true, since, $17-3 = 14$ is a multiple of $7$.
Also,
$3\equiv 17 \pmod{7}$ is true, since $3-17 = -14$ is divisible by $7$, the quotient is $-2$
- If $a\equiv b \pmod{n}$ and $b\equiv c \pmod{n}$ then $a\equiv c \pmod{n}$
Ex., Consider the congruences
$19\equiv 11 \pmod{4}$ and
$11\equiv 3 \pmod{4}$,
the congruence is
$19\equiv 3 \pmod{4}$ is also true.
- If $a\equiv b \pmod{n}$ and $c\equiv d \pmod{n}$, then $a+c\equiv b+d \pmod{n}$ and $ac\equiv bd \pmod{n}$
Ex., Consider the following congruences
$7\equiv 2 \pmod{5}$ .......(1)
$13\equiv 3 \pmod{5}$ .......(2)
Adding eq. $(1)$ and $(2)$ , we get
$7+13\equiv 2+3 \pmod{5}$
$20\equiv 5 \pmod{5}$, which is true.
Multiplying eq. $(1)$ and $(2)$, we get
$7*13\equiv 2*3 \pmod{5}$
$161\equiv 6 \pmod{5}$ , which is true.
- If $a\equiv b \pmod{n}$ , then $a+c\equiv b+c \pmod{n}$ and $ac\equiv bc \pmod{n}$
Ex., Consider the congruence
$17\equiv 1 \pmod{8}$ Adding 3 to both sides, we get
$17+3\equiv 1+3 \pmod{8}$
$20\equiv 4 \pmod{8}$
which is true , since $20 - 4 = 16$ is a multiple of $8$.
Now, multiplying 3 to both sides of
$17\equiv 1 \pmod{8}$, we get
$17*3\equiv 1*3 \pmod{8}$
$51\equiv 3 \pmod{8}$
which is true, since $51-3 = 48$ is a multiple of $8$.
- If $a\equiv b \pmod{n}$, then $a^k\equiv b^k \pmod{n}$, for any positive integer $k$.
Ex., Consider the congruence
$5\equiv 2 \pmod{3}$ On raising both sides with any positive integer, let it be $2$, we get
$5^2 \equiv 2^2 \pmod{3}$
$25 \equiv 4 \pmod{3}$, which is true.
Similarly, $5^4 \equiv 2^4 \pmod{3}$
$625 \equiv 16 \pmod{3}$
which is true, since, $625 - 16 = 609$ is a multiple of $3$.
- If $ca \equiv cb \pmod{n}$, then $a \equiv b \pmod{\frac{n}{d}}$, where $d=gcd(c,n)$
Ex., Consider the congruence $64 \equiv 28 \pmod{6}$
Letting $c=4$ and dividing, we get
$16 \equiv 7 \pmod 3$ because $64 \div 4 = 16$, $28 \div 4 = 7$, and $gcd(4, 6) = 2$
Comments
Post a Comment