2
$\begingroup$

If you have the following, where $a,b,c,d,$ and $z$ are unknown values while all other values are known, how do you solve for the actual numerical value of at least one of $a,b,c,d,$ or $z$. $m$ is a prime number.

$(p * a) \bmod m = z$

$(q * b) \bmod m = z$

$(r * c) \bmod m = z$

$(s * d) \bmod m = z$

Obviously,

$(p * a) \bmod m = (q * b) \bmod m = (r * c) \bmod m = (s * d) \bmod m$

All values, known and unknown, $\ne 0$ and $\ne 1.$

If additional examples are found then each other example would be identical except that the second variable (such as 'd') would be a new unknown value and each first variable (such as 'p') be a new known value. If it cannot be determined with these 4 examples then how many examples would I need to figure this out mathematically as opposed to testing virtually every possible value. How would one go about this? If you can, please answer in relatively layman's terms.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

No matter the values of $p,q,r,s$, in the above system, $a\equiv b\equiv c\equiv d\equiv z\equiv 0 \bmod m$ is a solution; so we can assume that $z\not\equiv 0 \bmod m$ to look for more solutions, which would also require that none of $p,q,r,s$ are divisible by $m$.

You specify that $m$ is a prime number. This means that, for $p\not\equiv 0 \bmod m$, there will be an inverse value $p^{-1}$ such that $p^{-1}p\equiv 1 \bmod m$.

Similarly $q^{-1},r^{-1},s^{-1}$ will exist. Then we can choose $z$ coprime to $m$ arbitrarily and calculate $a\equiv p^{-1}z,$ $b\equiv q^{-1}z,$ $c\equiv r^{-1}z$ and $d\equiv s^{-1}z \bmod m$ as a solution set corresponding to that $z$.


With your added condition of none of the variables being allowed to have values of $0$ or $1$, and taking as implied that all values are in the inclusive range $[2\ldots m{-}1]$, the choices may be a little more restricted but the above argument essentially holds. The modular inverses of $p,q,r,s$ will allow a suitable solution set for any $z$ not equal to any of the $p,q,r,s$.

For example, taking $m=7$ and $(p,q,r,s)=(2,3,4,5)$:
$2a \equiv 3b \equiv 4c \equiv 5c \bmod 7$

To avoid any of $a,b,c,d\equiv 1$, we need $z\equiv 6 \bmod 7$ (as the only permitted value left in range).

This then solves as $(a,b,c,d)\equiv (3,2,5,4) \bmod 7$

Another example: taking $m=17$ and $(p,q,r,s)=(3,8,11,14)$ (all calcs $\bmod 17$)

Then $z$ can be any of $(2,4,5,6,7,9,10,12,13,15,16)$. We can assess each quickly by first calculating $(p^{-1},q^{-1},r^{-1},s^{-1})\equiv(6,15,14,11)$ and then for example taking $z=10$ we can find $(a,b,c,d) \equiv (6\cdot 10,15\cdot 10,14\cdot 10,11\cdot 10)\equiv (9,14,4,8)$

$\endgroup$
6
  • $\begingroup$ What does "m [weird symbol] p" mean? You don't explain how we "arbitrarily" determine the value of "z". If I knew the value to "z" or a good 'fake' value, I would be able to solve for this, but each of the unknown variables have specific values that != 0 and != 1. In just one equation, Z could be anything from 1 to m just like a,b,c,and d. But in this situation, any value applied to "z" whether fake or the actual number would also have to be valid for each presented equation. $\endgroup$
    – Mine
    Commented Aug 23, 2017 at 18:45
  • $\begingroup$ The weird symbol $m\nmid p$ is "$m$ does not divide $p$", or in other words $p\not\equiv 0 \bmod m$. A simple upright $a\mid b$ is "$a$ divides $b$". When I say choose $z$ arbitrariliy, I mean that you will get a set of solutions from each such value of $z$ (usually $1\le z\le m{-}1$). Clarified my answer. $\endgroup$
    – Joffan
    Commented Aug 23, 2017 at 19:10
  • $\begingroup$ But how does one conclude that 6 is the appropriate value mathematically (rather than just going over the possible values). Your example seems simple as one can simply consider the actual values, but what mathematical method or steps would one use to handle any values such as p,q,r,s = (983,782,17,477) with m value of, lets say, 997? $\endgroup$
    – Mine
    Commented Aug 23, 2017 at 20:36
  • $\begingroup$ That would be a case where there are plenty of options for the value of $z$, all of which will lead to valid answer sets for $(a,b,c,d)$ $\endgroup$
    – Joffan
    Commented Aug 23, 2017 at 20:41
  • $\begingroup$ I see now where my confusion lies, I simplified the stuff I was working with to put on here. You proved that with the equations I've given, the unknown variables can be changed in each equation to account for whatever z value I decided to work with such that the equation always has a way of working. My fault, but you're right regarding the question I did ask. $\endgroup$
    – Mine
    Commented Aug 24, 2017 at 2:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .