How to solve nested congruences? 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! 
 A: 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)$
A: _
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
