Modular Arithmetic - Simultaneous Equation

• Apr 27th 2005, 04:40 AM
nicocsm
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?
• Apr 27th 2005, 09:34 AM
Shmuel
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?
• Apr 27th 2005, 09:52 AM
nicocsm
Re:
Yes, how to solve for k?
• Apr 27th 2005, 04:35 PM
MathGuru
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
• Apr 27th 2005, 04:41 PM
Math 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.
• Apr 28th 2005, 01:22 AM
nicocsm
Re:
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?
• Apr 28th 2005, 09:52 AM
Shmuel
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.