Is this problem an application of the cancelation law of congruences? Prove that if bd ≡ bd' (mod p), where p is a prime, and p does not divide b, then d ≡ d' (mod p)

Question

Is this problem an application of the cancelation law of congruences? Prove that if bd  ≡ bd' (mod p), where p is a prime, and p does not divide b, then d ≡ d' (mod p)

ganeshie8 · Answer

That follows trivially from euclid lemma :
$p\mid mn \implies p\mid m~~\text{or}~~p\mid n$

ganeshie8 · Answer

$$bd\equiv bd'\pmod{p} \implies p\mid b (d-d')$$
since $p\nmid b$, it must be the case that $p\mid (d-d')$

which is equivalent to saying $d\equiv d'\pmod{p}$

anonymous · Answer

ah.... I see. Is gcd(b,p) = 1 though?

ganeshie8 · Answer

$p\nmid b ~~\iff~~\gcd(p,b)=1 $

anonymous · Answer

so in general, m does not divide n if and only if gcd(m,n)=1?

ganeshie8 · Answer

that is correct only if $m$ is a prime

ganeshie8 · Answer

consider an example : $m = 4,~ n = 6$

$4\nmid 6$  but $\gcd(4,6)\ne 1$

ganeshie8 · Answer

btw, in this thread $p$ is assumed to be a prime.

anonymous · Answer

Ah... I see. Thank you :')

anonymous · Answer

So there are two ways to do the problem above. Euclid lemma or cancelation law (since gcd(b,p) = 1)

ganeshie8 · Answer

pretty sure there are many other ways to prove it, 
as you can see the proof is trivial

anonymous · Answer

right. Thank you :)