Question

Prove the following statements using either direct or contrapositive proof. If \(a \equiv b(\bmod n)\) and \(c \equiv d(\bmod n),\) then \(a c \equiv b d(\bmod n)\).

Short answer

The conclusion that \(ac \equiv bd (\bmod n)\) is proven via a direct algebraic manipulation of the given equalities.

Step-by-step solution

Set up the Proof

Firstly, using the given equations: \(a \equiv b(\bmod n)\) and \(c \equiv d(\bmod n),\) we can say that \(a = b + kn\) and \(c = d + ln\) for some integers \(k\) and \(l\).

Product of Equations

Multiply these two equations: \((b+kn)*(d+ln) = ac.\)

Proof of Congruency

Expand and rearrange the equation: \(bd + b ln + d kn + k l n^2 = ac\). We can write this congruence as \(ac \equiv bd (\bmod n)\) if we can factor out \(n\) from the right hand side. Rearranging terms, we get \(bd + n(b l + k d + k l n) = ac\), where \(b l + k d + k l n\) is also an integer. Therefore, we can conclude that \(ac \equiv bd (\bmod n)\).