# Result $a \equiv b \mod m$ or $c \equiv d \mod m$ is false $\Rightarrow ac \equiv cd \mod m$ is false? Root extraction $\mod m$

I know that $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$ implies $ac \equiv bd \pmod{m}$.

However, can one show that if $a \equiv b \pmod{m}$ is false, then:

$ac \equiv bd \pmod{m}$ is false, when $c \equiv d \pmod{m}$ is false.

and

$ac \equiv bd \pmod{m}$ is false, when $c \equiv d \pmod{m}$ is true.

That is the product of two congruences modulo $m$ is always false, if one of them is false ?

I need this result to understand how to extract roots modulo $m$.

$x^k \equiv b \pmod{m}$ has the solution $b^u$, since one can find $u, w$ such that: $x^k \equiv b \Rightarrow b^u \equiv (x^k)^u \equiv x^{1+\theta(m)w}\equiv x \pmod{m}$ where $\theta$ denote Euler's Totient function.

Here I see that $x$ is congruent to $b^u$ and $(x^k)^u$ but how to I do tell if $b^u \equiv (x^k)^u \Rightarrow x^k \equiv b \pmod{m}$ ?

Thanks for your time.

-
Did you mean $ab$ in place of $ac?$ – lab bhattacharjee Sep 15 '13 at 15:01
can you please cross check your first statement which is equivalent to $m|c(a-d)$ , But we don't know if $a\equiv d\pmod m$ or $d|c$ etc. – lab bhattacharjee Sep 15 '13 at 15:08
If you type \pmod{} instead of \mod{} you can also have the parenthesis around mod like the way it's written usually. – some1.new4u Sep 15 '13 at 15:17
Sorry, I edited it now. It should be $bd$ instead of $cd$ – Nicolas Lykke Iversen Sep 15 '13 at 16:34

## 3 Answers

We cannot. Note that $1\equiv 2\pmod{5}$ is false, as is $7\equiv 6\pmod{5}$, but $1\cdot 7\equiv 2\cdot 6$ is true.

(For the current question, which presumably has a typo, one can use $c\equiv 0\pmod{5}$.)

For extracting roots modulo $m$, there cannot be a full discussion unless we know more about $b$, $m$, and $k$. In many cases there are no solutions.

Remark: Suppose that $b$ and $m$ are relatively prime, and $k$ and $\varphi(m)$ are relatively prime. Then we can use Euler's Theorem to solve $x^k\equiv b\pmod{m}$.

For there exist integers $s$ and $t$ such that $sk+t\varphi(m)=1$. Then $$b^1=b^{sk+t\varphi(m)}=b^{t\varphi(m)}(b^s)^k\equiv (b^s)^k\pmod{m}.$$

-
This is the root i'm extracting with these assumptions. – Nicolas Lykke Iversen Sep 15 '13 at 16:39
The argument that I wrote out in the remark requires assumptions. We used $\gcd(b,m)$ to ensure that $b^{\varphi(m)}\equiv 1$. And we used $\gcd(k,\varphi(m))=1$ to be able to use Bezout's Theorem. We did not use or need anything about "if $a\not\equiv\dots$." – André Nicolas Sep 15 '13 at 16:44
Your explanation is clear why $b^s$ is a solution to the congruence. However what confuses me is the book: "We have that $x = b^u$ is a solution to the congruence $x^k \equiv b (\mod m)$ since $b^u \equiv (x^k)^u \equiv x^{1+\theta(m)w} \equiv x (\mod m)$ (1)" Im having difficult seeing why it is obvious $b^u$ is a solution due to (1) ? Here the assumptions are the same as you wrote above. Can you help ? – Nicolas Lykke Iversen Sep 15 '13 at 16:57
They wrote basically the same thing. Their Bezout equation is $uk-w\varphi(m)=1$. – André Nicolas Sep 15 '13 at 17:06
Yes, but then I have $b^u \equiv ((b^u)^k)^u (\mod m)$. How can I deduce from this that $b \equiv (b^u)^k (\mod m)$ ? I need to remove a power of $u$ from both sides, and I can only do this if I know $b \equiv (b^u)^k (\mod m)$ and how do I know this is true ? If I know it is true, I can mulple both sides repeatedly to get $b^u \equiv ((b^u)^k)^u (\mod m)$. – Nicolas Lykke Iversen Sep 15 '13 at 17:09

An alternative to the example of André Nicolas is to consider the case $a \not\equiv b \operatorname{mod} m$ and $0 \equiv 0 \operatorname{mod} m$.

In general, your last statement is false. That is, if $a^n \equiv b^n \operatorname{mod} m$, then it is possible that $a \not\equiv b \operatorname{mod} m$. For example, $1^2 \equiv 1 \operatorname{mod} m$ and $(m-1)^2 \equiv 1 \operatorname{mod} m$, but for $m > 2$, $1 \not\equiv m-1 \operatorname{mod} m$.

-
In that last example, of course one requires $m>2$... – Asaf Karagila Sep 15 '13 at 16:35
@AsafKaragila: Of course. I meant in general but I will make that clear. – Michael Albanese Sep 15 '13 at 16:54

Isn't this as simple as noting that $1\cdot k \equiv k\cdot 1\pmod m$ for all $k$? So if we take $k$ such that $k\not\equiv 1\pmod m$ then we have a counter-example to your claim.

-
I'm asking if $a \equiv b (\mod m)$ is false, then is $ac \equiv bd (\mod m)$ false if $b \equiv d (\mod m)$ is true or false. – Nicolas Lykke Iversen Sep 15 '13 at 16:41
That might be what you meant to ask, but that is not what you asked. – Thomas Andrews Sep 15 '13 at 16:50
Specifically, if $a=d=k$ and $b=c=1$ and $k\not\equiv 1\pmod m$ then $a\not\equiv b\pmod m$ and $c\not\equiv d\pmod m$ but $ac\equiv bd\pmod m$. – Thomas Andrews Sep 15 '13 at 16:53