## anonymous one year ago 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)

1. ganeshie8

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

2. ganeshie8

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

3. anonymous

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

4. ganeshie8

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

5. anonymous

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

6. ganeshie8

that is correct only if $$m$$ is a prime

7. ganeshie8

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

8. ganeshie8

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

9. anonymous

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

10. anonymous

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

11. ganeshie8

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

12. anonymous

right. Thank you :)