3
$\begingroup$

Let's say that I'm trying to solve this equation to find the valid value(s) of x:

$(x \% 5) \% 2 = 1$

I know that when you have:

$A\%B=C$

That you can rewrite it this way:

$A \equiv C+B*N$
$\forall N \in \mathbb{Z}$

So, to solve the equation, I first transform it to this:

$x\%5\equiv 1+2*N_0$

I then transform it again to get this:

$x\equiv 1+2*N_0+5*N_1$

That equation works when $N_0$ and $N_1$ are 0 ($x=1$), it also works when they are 1 ($x=8$).

However, when $N_0$ is $2$ and $N_1$ is 3 it doesn't work ($x=20$).

Can anyone tell me where I've went wrong?

Thanks!

$\endgroup$
3
$\begingroup$

Stranger things happen when you use $\% p$ as an operator that sends elements to the canonical representative of their equivalence class $\text{mod}~p$.

Instead, I recommend thinking of it in this way: since the outer operation is $\%2$ and this equals $1$, we know that we are looking for those elements $x$ such that $x\% 5$ are odd. Note that for any $x$, $x\equiv x~\text{mod}5$ as well as $x\equiv x+5~\text{mod}5$, so they are all simultaneously equivalent to both even and odd numbers.

Instead, since we are treating $\% 5$ as an operator that sends things to their canonical representative for their equivalence classes (i.e. as a function from $\mathbb{Z}$ to $\{0,1,2,3,4\}$), we see then that we are looking for those $x$ which are either $x\equiv 1~\text{mod}5$ or $x\equiv 3~\text{mod}5$.

I.e. the solution set will be $(5\mathbb{Z}+1)\cup (5\mathbb{Z}+3) = \{\dots,-7,-4,-2,1,3,6,8,11,13,16,18,21,23,\dots\}$

In the hopes of seeing a more convenient way of writing the answer, we attempt to write this as $\{x~|~x = 5n +2\pm 1\}$

I am unsure of a more general method at the moment, but will probably think about it as it is somewhat interesting.


To explain further how to generalize the method I suggested, suppose we are looking at $(x\%n)\%k=r$ (assuming each number is positive).

By looking at the outer $\%$ first, we see that we are looking for those $x$ for which $(x\%n)$ is $r\text{mod}k$. Let us color those in our list:

$\{0,1,2,\dots,r-1,\color{red}{r},r+1,\dots,k+r-1,\color{red}{k+r},k+r+1,\dots,lk+r-1,\color{red}{lk+r},lk+r+1,\dots,n-1\}$ (where $l$ is some integer)

The solution set will then be $(n\mathbb{Z}+r)\cup (n\mathbb{Z}+k+r)\cup\dots\cup (\mathbb{Z}+lk+r)\cup\dots$

Which can be written more compactly as:

$$\bigcup\limits_{\{l\in\mathbb{Z}~|~0\leq lk+r\leq n-1\}}(n\mathbb{Z}+lk+r)$$

where again $l$ is restricted to being an integer.

In the given example, the solution set is $(5\mathbb{Z}+0\cdot 2+1)\cup (5\mathbb{Z}+1\cdot 2+1)$

If it were instead $(x\%14)\%3=2$ the solution set would be $(14\mathbb{Z}+3\cdot 0+2)\cup(14\mathbb{Z}+3\cdot 1+2)\cup(14\mathbb{Z} +3\cdot 2+2)\cup(14\mathbb{Z}+3\cdot 3+2)$

or more compactly as $(14\mathbb{Z}+2)\cup(14\mathbb{Z}+5)\cup(14\mathbb{Z} +8)\cup(14\mathbb{Z}+11)$

$\endgroup$
  • $\begingroup$ Is there a way to generalize this at all? This is a specific problem of a more general set I'm trying to be able to solve, where it'll be % a variable, instead of a constant (at least for the inner mod). Thanks!! $\endgroup$ – Alan Wolfe Sep 13 '15 at 22:46
  • $\begingroup$ @AlanWolfe Generalized the method I described above in my edit. $\endgroup$ – JMoravitz Sep 13 '15 at 22:56
  • $\begingroup$ Slowly but surely I'm mentally reconciling the method I was aiming at and the method you've described. thanks a bunch, it is an interesting thing :p $\endgroup$ – Alan Wolfe Sep 14 '15 at 0:10
  • $\begingroup$ I think l is in Z, and only limited such that lk+r is less than n. (Aka its in mod n) $\endgroup$ – Alan Wolfe Sep 14 '15 at 2:29
  • 1
    $\begingroup$ @AlanWolfe Ah, yes. That is what I intended. Fixing the bounds now. $\endgroup$ – JMoravitz Sep 14 '15 at 2:32
1
$\begingroup$

_ Hi again Alan, we're both working on multiple modulo problems.

When $N_0=2$, $x\%5\equiv 1+2*N_0\equiv 5$. But $5 \equiv 0 \left(mod\ 5\right)$

You are looking for a generator function. $(x \% 5) \% 2 = 1$ has solutions $x \equiv 1,3 \left(mod\ 5\right)$ by trial.

$x_1(k) = 1 + 2((k+1)\%2) + 5\lfloor{\frac{k-1}{2}}\rfloor$ for $k = 1\dots\infty$

Similarly for $(x \% 5) \% 2 = 0$ has solutions $x \equiv 0,2,4 \left(mod\ 5\right)$ by trial.This has order 3.Its generator function is:

$x_0(k) = 2((k+2)\%3) + 5\lfloor{\frac{k-1}{3}}\rfloor$ for $k = 1\dots\infty$

The way to find these generator functions is to find solutions (mod 5) by trial. If the number of solutions is $s$ then that will give you the $5\lfloor{\frac{k-1}{s}}\rfloor$ term.x jumps up by 5 every $s$ steps.The left term will be %$s$ so that it cycles through the solutions (mod 5).I don't have an exact method for finding the left term.Try adding an offset to k to change the order of numbers %$s$.

If you need negative $x_t$ values as well then $x_t(k) - 5c$ should work.

How to solve simultaneous modulo equations? I'm still working on it.

regards arthur

$\endgroup$
  • 1
    $\begingroup$ Since asking this question I came up with this: blog.demofox.org/2015/09/15/solving-nested-modulus-equations still working out multiples too, as well as when the variable is on the right side of the % sign, especially when nested! I might have solved the main thing I was trying to get at though from the other question, using the CRT to solve unnested modulus equations that are a subset of the nested solutions. Pretty stoked, my searchight be over (for now hehe). $\endgroup$ – Alan Wolfe Sep 26 '15 at 4:49
  • 1
    $\begingroup$ Good link,thnx. if $a \equiv r\left(mod\ x\right)$ then $a - r\equiv 0\left(mod\ x\right)$ so $x | (a-r)$. i.e. $x$ is a factor of $a-r$. Finding factors of integers requires a search e.g. quadratic sieve, number field sieve. $\endgroup$ – arthur Sep 26 '15 at 6:34
  • $\begingroup$ Thanks a ton, I'll check those out! $\endgroup$ – Alan Wolfe Sep 26 '15 at 6:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.