I've recently learned about some modular congruence, but I'm having trouble actually solving problems. I've tried a few references--http://www.math.cornell.edu/~putnam/modular.pdf gets pretty close, but I'm still a bit confused.
For example, let's say I have $$6a\equiv 10b \mod{14}$$
What else can I say is true? Can I just divide everything by a factor? For example, is $$3a \equiv 5b \mod{7}$$
By experimentation, I think the above is true.
So then, I can just divide everything by the same number. But, in the example below (which I think is true?) I divide x and y by 26, but I don't change the mod $$26x \equiv 26y \mod{5}$$ and therefore $$x \equiv y \mod{5}$$
Answer
Yes, the two things are both true.
The first one is:
$$ad \equiv bd \pmod{nd}$$
if and only if
$$a \equiv d \pmod{n}$$
This happens because
$$dn |d(a-b) \Leftrightarrow n |a-b$$
The second is a completely different fact, which happens for a different reason:
If
$$ad \equiv bd \pmod{n } \mbox{ and } gcd(d,n)=1 \mbox{then} \\
a \equiv b \pmod{n}$$
This is because $n|d(a-b)$ and $gcd(n,d)=1$ implies $n|a-b$.
No comments:
Post a Comment