Thread: Modular Arithmetic - Simultaneous Equation

Hi,

I am having some problems trying to solve this:

k+a mod n = x
k+b mod n = y

where n, a, b, x and y is known integers and n is prime number
Is there a way to find k?

k+a mod n = x
k+b mod n = y

Can be written as:

x - (k+a) is evenly divisible by n
y - (k+b) is evenly divisible by n

Do you agree? now we try to solve for k?

Yes, how to solve for k?

How about dividing (x-a) by n and finding the remainder
and also dividing (y-a) by n and finding the remainder

Both should give you the value of k

unless k>n

think about it . . . if k was 9 and n was 5 then your method would give k=4

essentially you would know that k=remainder + p*n and p could equal 0,1,2,3 etc.

hmm...
So,

(k+a) mod n = x
(k+b) mod n = y

k+a = x + np
k+b = y + nq

where p and q could be 0,1,2,3...

is there any way to find k without having to substituting in the p and q values to see if they match?

I think you have 2 equations and 3 unknowns. p, q, and k are unknown.
Maybe someone has a slick way to do it though.