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?

Printable View

- April 27th 2005, 03:40 AMnicocsmModular 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? - April 27th 2005, 08:34 AMShmuel
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? - April 27th 2005, 08:52 AMnicocsmRe:
Yes, how to solve for k?

- April 27th 2005, 03:35 PMMathGuruHow about this?
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 - April 27th 2005, 03:41 PMMath Help
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. - April 28th 2005, 12:22 AMnicocsmRe:
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? - April 28th 2005, 08:52 AMShmuel
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.