Properties of Congruences

97 Views Asked by At

For context:

The question/answer is given as follows:

Show by induction that if n is a positive integer, then $4^n ≡ 1 + 3n (\text{mod } 9)$.

For the base case, $4 ≡ 1+3 (\text{mod } 9)$.

For the induction hypothesis, assume that $4n ≡ 1+3n (\text{mod } 9)$ for some positive integer n.

Then:

$4^{n+1} = 4^n \cdot 4 ≡ 4(1 + 3n) = 4 + 12n \equiv 4 + 3n \equiv 1 + 3(n + 1) (\text{mod } 9)$.

Therefore $4^n ≡ 1 + 3n (\text{mod } 9)$ for all positive integers $n$.

Question:

What property allows you to show that: $4 + 12n \equiv 4 + 3n \ (\text{mod } 9)$? I can plugin numbers and show, but this is not very constructive. I also note that:

$ 4+12n \equiv 4+3n \ (\text{mod } 9) \Rightarrow 9 | (4+12n)-(4+3n) \Rightarrow 9 | 9n $.

If I was not given $4+3n$ to begin with, I don't know if I could have concluded that result.

2

There are 2 best solutions below

0
On BEST ANSWER

The taking of modulus respects multiplication and addition. So if $a\equiv b\bmod n$, then $a\cdot c\equiv b\cdot c\bmod n$ and $a+c\equiv b+c\bmod n$ for any integer $c$.

In your case, $12\equiv 3\bmod 9$, so $4+12n\equiv 4+3n\bmod 9$.

1
On

The modulus property allows you to convert 12 to 3 in $\mathbb{Z}_9$. It is called congruence representation.

What is your second problem?