Solved

equation with modulo, has a general solution?

Posted on 2011-02-11
16
395 Views
Last Modified: 2012-05-11
a = (x*c) (mod b)
a, c, b are known positive naturals, can anyone tell how to calculate x?
0
Comment
Question by:ravenpl
  • 3
  • 3
  • 3
  • +4
16 Comments
 
LVL 27

Expert Comment

by:d-glitch
ID: 34874425
There may not be a solution if b and c are not relatively prime.

   ==>  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
0
 
LVL 27

Assisted Solution

by:aburr
aburr earned 100 total points
ID: 34874444
The answer to your problem is straight forward but complicated to write. One has little trouble with the definition of division. But generalized modulo arithmetic is more complicated. In you r case
x = a/c          but the arithmetic is to be mod (b)
You need the definition of “mod”.  Mod is a function of two natural numbers which returns the remainder after the number m is subtracted from n so many times that the difference would change its sign if further subtractions were made. That is
n(mod(m) = m * frac(n/m)
 where the function frac(y) = y – [y] where the function [y] = the integer part of y.
Thus in your particular case
 X = b * (a/c – [a/c])
I know it is messy, but there are not simpler common standard symbols defined to simplify the notation. However you have your general answer.
0
 
LVL 73

Accepted Solution

by:
sdstuber earned 250 total points
ID: 34874488
assuming that was supposed to be written as

a = ((x*c) mod b)

or

a = (x*c) mod b


then x will be one of a subset of values of this form


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





0
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
LVL 43

Author Comment

by:ravenpl
ID: 34874609
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?
0
 
LVL 27

Expert Comment

by:aburr
ID: 34874691
I do not see how if a =  0 and c =10     x can be other than 0.
0
 
LVL 27

Expert Comment

by:aburr
ID: 34874695
zeros are messy anyway
0
 
LVL 73

Expert Comment

by:sdstuber
ID: 34874743
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

0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34874862
>>  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, ....
0
 
LVL 84

Expert Comment

by:ozo
ID: 34874865
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 34874879

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

Author Comment

by:ravenpl
ID: 34874898
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.
0
 
LVL 37

Assisted Solution

by:TommySzalapski
TommySzalapski earned 150 total points
ID: 34875317
" assuming x=10 c=10 b=10 "
But if b and c are relatively prime then this can't happen.
Since they are all naturals, there are no 0s to worry about (remember, naturals are the whole numbers except 0).
So all the numbers are integers >= 1 and b is relatively prime to c.
So the solution is going to be x = y + n*b where n = 0,1,2,3,4,... and y is the minimum value of x that solves the problem.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34875385
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.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34875410
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
0
 
LVL 32

Expert Comment

by:phoffric
ID: 34876684
>> a = (x*c) (mod b)
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.
0
 
LVL 43

Author Comment

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

Featured Post

ScreenConnect 6.0 Free Trial

Check out the updates in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI that improves session organization and overall user experience. See the enhancements for yourself!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
How to solve this equation 3 53
Word Problem 4 82
Need a nodal sequencing tool 3 93
cone shaped white flowers (perhaps like easter lily..) 8 51
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question