Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
show 3 more comments

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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