- #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 ##.