hey i'm a little stuck on this question, I can seem to do it fine when actual values are being used but can't quite get an answer/know what I'm meant to be writing down as an answer for this question:
Set h = gcd(a,n)
If h does not divide b, then prove that ax = b(mod n) has no
integer solutions for x.
All i've managed to do is write h in terms of a and n using other parameters and saying there should be h solutions to it if there were any..not even sure if this is right?! Help!
Turn on thread page Beta
mod help watch
- Thread Starter
- 27-01-2009 21:35
Offline14ReputationRep:Wiki Support Team
- Wiki Support Team
- 28-01-2009 04:28
Ok. Messy, but:
We know that ax = np + b (*) for some integer p (why?). Now, let qh = a, rh = n, where q and r are integers (why can we do this?). Then we can rewrite (*) as...