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?
Follow Math Help Forum on Facebook and Google+
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.
View Tag Cloud