# How to solve for b in a = b mod q

Tags:
1. Feb 25, 2015

### John Harris

1. The problem statement, all variables and given/known data
How do I solve for b in a= b mod q

2. Relevant equations
I'm not sure what mod operations for equations are allowed. I would like to know.

3. The attempt at a solution
Unsure how to move the mod q to the other side.

2. Feb 25, 2015

### Simon Bridge

Back up a bit:
Pick some numbers for a and q, and see what values of b will make the relation true.
i.e. 1 = b mod 2

Try for some other numbers?
What do you notice?

3. Feb 25, 2015

### John Harris

Got to make sure I work for it... Any odd number. b divides q-a

4. Feb 25, 2015

### Simon Bridge

Good - you just solved the problem for a specific example.
Next step is to see if you can generalize.

5. Feb 25, 2015

### John Harris

b=qk+a

But I don't understand how they did it here. They solved for x without removing the mod or adding a k.
s = k-1 (H(m) + x*r) mod q
x
= ((s * k) – H(m)) * r-1 mod q

6. Feb 25, 2015

### Simon Bridge

Go through it one step at a time - make sure you know what each bit means.

7. Feb 25, 2015

### John Harris

s = k-1 (H(m) + x*r) mod q

I see how they got it to ((s * k) – H(m)) * r-1= x mod q
But I don't see how they get it farther. If I knew I wouldn't be asking for help. I'm just asking for the simple equation property that they used. This isn't a HW assignment. I don't have time to derive it myself. What you asked me to do hasn't helped.

8. Feb 25, 2015

### SammyS

Staff Emeritus
Are you saying that you can get from
s = k -1 (H(m) + x*r ) mod q
to
((s*k ) – H(m)) * r -1 = x mod q ,​

but you can't solve that for x ?

Well, if a ≡ b mod q, then b ≡ a mod q . Right?

9. Feb 25, 2015

### John Harris

But this is an equality not a congruence.
3=19 mod 8
19≠3mod 8

10. Feb 26, 2015

### SammyS

Staff Emeritus
Yes, I overlooked the ' = ' sign.

Last edited: Feb 26, 2015
11. Feb 27, 2015

### SammyS

Staff Emeritus
True, but the solution to the equation, $\ 3=x\mod 8 \,,\$ is $\ x=3+8n \$.

The mod function is periodic, so there are many solutions for x . One of the solutions is 3 itself. For that solution it is true that $\ x=3\mod 8 \$.
What they are doing here is certainly strange. What information, if any, do we know regarding, H(m), r, and k ?