ravenpl

asked on

# equation with modulo, has a general solution?

a = (x*c) (mod b)

a, c, b are known positive naturals, can anyone tell how to calculate x?

a, c, b are known positive naturals, can anyone tell how to calculate x?

SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

ASKER CERTIFIED SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

ASKER

sdstuber: I came with Your solution, but how to tell which n is OK?

aburr: assuming x=10 c=10 b=10 a eq 0; b * (a/c – [a/c]) render x=0 instead of 10?

aburr: assuming x=10 c=10 b=10 a eq 0; b * (a/c – [a/c]) render x=0 instead of 10?

I do not see how if a = 0 and c =10 x can be other than 0.

zeros are messy anyway

if X is an integer then I don't know how to determine valid "n" in general.

I made the assumption that X was supposed to be a natural like a,b,c

but, on second reading your requirement didn't specify that,

so, as long as c is not 0, I think you can use

x = (a + nb)/c where n is 0,1,2,3...

for all n

I made the assumption that X was supposed to be a natural like a,b,c

but, on second reading your requirement didn't specify that,

so, as long as c is not 0, I think you can use

x = (a + nb)/c where n is 0,1,2,3...

for all n

>> I do not see how if a = 0 and c =10 x can be other than 0.

If a = 0 and c =10 and b = 100 x can be 10, 20, 30, ....

If a = 0 and c =10 and b = 100 x can be 10, 20, 30, ....

If a = 1 and c = 9 and b = 10 x can be 9, 19, 29, 39, ....

ASKER

OK, x is natural as well. Additionally c is prime if it matters(relatively to b). I think You should have now the whole picture. The function is quite simple hashing function(x as an input). What I need is to invert it.

ozo: that what I was afraid of, browsing the internet was leading there...

OK, let me try the iteration algo - looks simplest, yet lots of divisions.

ozo: that what I was afraid of, browsing the internet was leading there...

OK, let me try the iteration algo - looks simplest, yet lots of divisions.

SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Of course if a >= b then there is no solution. Otherwise, there is one. If you look at the pattern, when you start x at 1 and keep increasing it, the values of a cycle through the numbers [0,b-1] in some fashion. Each number in that range appears once in the cycle and the same cycle repeats infinitely. So all you have left to do is find where you need to start (based on a).

I see no need to restrict a from being 0 but it doesn't really matter.

I see no need to restrict a from being 0 but it doesn't really matter.

Uh, there's no need to restrict x to the naturals either. As long as you are okay with negatives in modulo arithmetic (-1 mod 10 is 9).

So the solution will actually be in the form x = y + n*b where n is any integer and y is in the range of [0,b-1]

Here's the spreadsheet I've been playing with.

modulo.xls

So the solution will actually be in the form x = y + n*b where n is any integer and y is in the range of [0,b-1]

Here's the spreadsheet I've been playing with.

modulo.xls

>> a = (x*c) (mod b)

If you are you talking about a Congruence relation, then

If you are you talking about a Congruence relation, then

*a*can be greater than*b*. For example, 38 == 14 mod 12 since 12 divides evenly into 38-14 (i.e., 24); or, alternatively, 38 mod 12 = remainer of 2 and 14 mod 12 = remainder of 2, so 38 == 14 mod 12.ASKER

OK, I ended in iterating n in [0..c] range for x=(a + nb)/c - so far so good. Thanx for Your input.

==> c =5 and b = 10 yields solutions only for a = 0 [x = even] and for a = 5 [x = odd]

There are no solutions for a = 1,2,3,4,6,7,8,9