How to solve nested congruences?

Question

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!

Answer 1

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)$

Answer 2

_ 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