- #1

Math100

- 779

- 220

- Homework Statement
- Prove the following assertion:

If ## a\equiv b \mod n ## and the integers ## a, b, n ## are all divisible by ## d>0 ##, then ## a/d\equiv b/d \mod n/d ##.

- Relevant Equations
- None.

Proof:

Suppose ## a\equiv b \mod n ## and the integers ## a, b, n ## are all divisible by ## d>0 ##.

Then ## n\mid (a-b)\implies mn=a-b ## for some ## m\in\mathbb{Z} ##.

Note that ## a=id\implies \frac{a}{d}=i ##, ## b=jd\implies \frac{b}{d}=j ##, and ## n=kd\implies \frac{n}{d}=k ## for some ## i, j, k\in\mathbb{Z} ##.

Thus ## id-jd=m(kd)\implies i-j=mk\implies \frac{a}{d}-\frac{b}{d}=m\frac{n}{d}\implies \frac{a}{d}\equiv \frac{b}{d} \mod \frac{n}{d} ##.

Therefore, if ## a\equiv b \mod n ## and the integers ## a, b, n ## are all divisible by ## d>0 ##, then ## a/d\equiv b/d \mod n/d ##.

Suppose ## a\equiv b \mod n ## and the integers ## a, b, n ## are all divisible by ## d>0 ##.

Then ## n\mid (a-b)\implies mn=a-b ## for some ## m\in\mathbb{Z} ##.

Note that ## a=id\implies \frac{a}{d}=i ##, ## b=jd\implies \frac{b}{d}=j ##, and ## n=kd\implies \frac{n}{d}=k ## for some ## i, j, k\in\mathbb{Z} ##.

Thus ## id-jd=m(kd)\implies i-j=mk\implies \frac{a}{d}-\frac{b}{d}=m\frac{n}{d}\implies \frac{a}{d}\equiv \frac{b}{d} \mod \frac{n}{d} ##.

Therefore, if ## a\equiv b \mod n ## and the integers ## a, b, n ## are all divisible by ## d>0 ##, then ## a/d\equiv b/d \mod n/d ##.