0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What pattern?${}$ $\endgroup$ – Andrés E. Caicedo Feb 1 '18 at 23:00
  • $\begingroup$ The variables $x,y$ do not seem to be related to the variables $a,b$. $\endgroup$ – астон вілла олоф мэллбэрг Feb 1 '18 at 23:01
  • $\begingroup$ Sorry about that! I've modified the question to hopefully be more clear. The pattern I was referring to is dividing everything by the same number, including the mod. $\endgroup$ – CalendarJ Feb 1 '18 at 23:03
  • 1
    $\begingroup$ You aren't dividing by $26$ - you're reducing $26 \bmod 5$. $\endgroup$ – Joffan Feb 1 '18 at 23:05
  • $\begingroup$ Ah, yes, you can always divide through the mod. But sometimes you don't have to. But only sometimes. $\endgroup$ – fleablood Feb 1 '18 at 23:42
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Okay, this is starting to make sense. One thing that will help me: what does the | mean? Since I don't know the name, I'm not sure how to google it. -- Edit: Found it. math.stackexchange.com/questions/1041019/… $\endgroup$ – CalendarJ Feb 1 '18 at 23:08
  • $\begingroup$ $a|b$ means $a$ divides into $b$ evenly. So $a|b$ means that $b = ka$ for some integer $a$. It's a very useful, notation. $\endgroup$ – fleablood Feb 1 '18 at 23:40
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.