Properties of modular arithmetic

Question

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 1

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

Answer 2

Oops, I misunderstood your question.

Yes, If $a*b \equiv a*c \mod n*a$ then $b \equiv c \mod n$. And that is easy to check.

$a*b = a*c + K(n*a) \implies b =c + Kn \implies b\equiv c\mod n$.

You can sometimes take this further.

$a*b\equiv a*c \mod W$. Let $d= \gcd(a,W)$ and let $W = d*W'$. and let $a = d*a'$.

$a*b = a*c + KW = a*c + K*d*W'$

$b = c + \frac {K*d*W'}{a} = c + \frac {K*d*W'}{da'} = c + \frac {K*W'}{a'}$

Now $a' $ and $W'$ have no factors in common so $a'$ must divide $K$.

So

$b = c + \frac K{a'} * W'$

So $b \equiv c \mod \frac {W}{\gcd(a,d)}$.

So you don't have to divide all the moduls. Just by the greatest common divisor.

=======

Can I just divide everything by a factor?

NO! That's HUGE Trap. But consider

$2*4 \equiv 2 \mod 6$ but $4 \not \equiv 2\mod 6$.

And we can see why this doesn't work.

$a*b \equiv c \mod n$ means $ab = c + Kn$. If $a|c$ we have $b = \frac ca + \frac {Kn}a$ so $a|Kn$ but that doesn't mean $\frac {Kn}a$ is a multiple of $n$! Becuase $a$ and $n$ can have a factor in common that "divides out".

To see this.

$8 \equiv 2 \mod 6$ so

$8 = 2 + k6$. This is true.

$8 = 2 + (1)*6$

$\frac 82 = \frac 22 + \frac {1*6}2$

$4 = 1 + \frac 12*6$ but $\frac 12$ is NOT an integer. So we can't so $4 \equiv 1 \mod 6$.

Instead the $2$ divides the $6$ ITSELF!

So $4 = 1 + 1*3$.

And we get $4 \equiv 1 \mod 3$. That's okay... but $3$ isn't $6$ so that's not the same thing.

But you can do it if the number you are dividing by and the modulus are relatively prime.

So if $a*b \equiv c \mod n$ and $a|c$ !!!AND!!! $\gcd(a,n) =1$ then we can do:

$a*b = c+Kn$

$b = \frac ca + \frac {Kn}a$ so $\frac {Kn}a$ is an integer.

!!!BUT!! $a$ and $n$ have no factor in common so $a|K$ and $\frac Kn$ is an integer.

So $b = \frac ca + \frac {K}a*n$.

So $b \equiv \frac ca \mod n$.

.....

And we can also do this:

If $ab \equiv c \mod n$ and $a|c$ then we can say:

$b \equiv c \mod \frac n{\gcd(a,n)}$.

This is because:

$ab \equiv c \mod n$ means

$ab = c + kn$

$b = \frac ca + \frac {kn}{a}= \frac ca + \frac {k\frac n{\gcd(a,n)}\gcd(a,n)}{\frac a{\gcd(a,n)}\gcd(a,n)}=\frac ca + \frac {k\frac n{\gcd(a,n)}}{\frac a{\gcd(a,n)}}=$

As $n' = \frac n{\gcd(a,n)}$ and $a'=\frac a{\gcd(a,n)}$ have no common factors in common we have $a'|k$, and:

$b = \frac ca + \frac k{a'} n'$

So $b \equiv \frac ca \mod n'$.

Example $36*47\equiv 18 \mod 27$ means

$2*47 \equiv 1 \mod \frac {27}{\gcd(27,18)}$

$94 \equiv 1 \mod 3$.

But $94 \not \equiv 1 \mod 27$.