4
$\begingroup$

Prove that for $n$ in the set of natural numbers, with $n \geq 2$: For all $a, b \in \mathbb{N}$, $a \equiv b \mod n$ implies that $a^2 \equiv b^2 \mod n$.

also what about this Prove by induction that for $n$ in the set of natural numbers, $n \geq 2$ For all $a,b \in \mathbb{N}$, $a \equiv b \mod n$ implies that $a^k \equiv b^k \mod n$.

$\endgroup$
1

5 Answers 5

8
$\begingroup$

Note that you have that $$a^k - b^k = (a-b)(a^{k-1} + a^{k-2}b + \ldots + ab^{k-2} + b^{k-1}).$$

Now if $a \equiv b \mod n$, then we have that $a = b + kn$ for some $k \in \mathbb{Z}$ and hence we have that $a - b = kn$. Therefore we have that $$n \mid (a-b)$$ and this implies that $$n \mid (a-b)(a^{k-1} + a^{k-2}b + \ldots + ab^{k-2} + b^{k-1}) = a^k - b^k.$$ Therefore, we have that $rn = a^k -b^k$ for some $r \in \mathbb{Z}$ and hence $$a^k \equiv b^k \mod n.$$

$\endgroup$
1
  • 1
    $\begingroup$ I have corrected the exponents of my first expression (since I made an error over there). This should make my proof correct. However, I have no idea on why you had to prove this using induction. Was this the problem statement or was this your first idea on how to solve this? (just curious) $\endgroup$
    – Student
    Commented Mar 9, 2017 at 14:53
4
$\begingroup$

$a\equiv b\pmod{n}\iff n\mid a-b$

$\implies n\mid (a-b)(a+b)=a^2-b^2\iff a^2\equiv b^2\pmod{n}$

$\endgroup$
1
  • $\begingroup$ this is a special case k = 2. $\endgroup$
    – john
    Commented Sep 14, 2020 at 4:47
2
$\begingroup$

I hope that you are not required to use induction to prove this, since it's a very special case of a standard theorem at the start of studying modular arithmetic:

If $$a \equiv a' \pmod{n}$$ and $$b \equiv b' \pmod{n}$$ then $$a+b \equiv a'+b' \pmod{n}$$ and $$ab \equiv a'b' \pmod{n} .$$

$\endgroup$
0
$\begingroup$

$a\equiv_n b\implies a-b\equiv_n 0$. What does this say about $n $ being a factor of $a-b $?

If we factor $a^2-b^2$, is there anything we can use from what I just previously mentioned to show the congruence?

$\endgroup$
0
$\begingroup$

Okay, so first let's make a preposition for a^k ≡ b^k, and let's call it P(k). Once we have that, we can move on to our base case. Our base case would be P(0), or when a^0 ≡ b^0 (mod m). That would equal 1 ≡ 1 (mod m). That is true, since, based off of definition, m | (1 - 1), and that equals m | 0, which is true, since m * 0 = 0, so our base case is true. Now it is time for the inductive step. For whenever k ≥ 0, we would have to assume that P(k) in order to prove that P(k + 1) is true. So then assume that a^k ≡ b^k (mod m) is true. When we combine these assumptions and the fact that if a ≡ b (mod m) and c ≡ d (mod m) are true, then a + c ≡ b + d (mod m) would also be true, we would get a^(k + 1) ≡ b^(k + 1) (mod m), so this would therefore be proven by using proof by induction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .