How to find elements of a ring $\mathbb{Z}_n$ in Mathematica

Question

How to find elements of a commutative ring with unity $\mathbb{Z}_n$, (under addition and multiplication modulo $n$) by using Mathimatica, which satisfying the following condition. Let $x, y \in R = \mathbb{Z}_n$ be two nonzero elements such that $xy = x$, here $y \neq 1$. Please guide me how to find all such $y \in \mathbb{Z}_n$. Manually I can do this but it take too much time for big rings like $\mathbb{Z}_{60}$ thats why I need to find these elements by using mathematica. hope you understand.

Answer 1

If you want to list just the values $y$, then you can find the prime factors of $n$ and the find any $y$ such that $y-1$ is divisible by one of those prime factors.

For $n=60$, the primes are $2,3,5$. You can list the even numbers first:

$$y-1=2,4,6,\dots 58 \text{ or }\\ 3,9,15, 21, \dots, 57\text{ or }\\ 5,25,35,55 $$

if you want to list all solutions $(x,y)$:

I'm not sure about Mathematica, but this approach might work better than trial and error. It enumerates all pairs $x.y$ that solve the equation.

For each integer $x$, compute $\gcd(x,n)$. Then we have that $y-1$ can be any multiple of $\frac{n}{\gcd(x,n)}$. Give that you want $y-1\neq 0$, this gives ${\gcd(x,n)}-1$ values of $y$ for any $x$.

So the pseudo-code would look something like:

for x in (0..(n-1)) {
    g=gcd(x,n)
    y1=n/g
    for k in (1..(g-1)) {
        y = k*y1+1
        ... emit pair (x,y) ...
    }
}

You might want to exclude the case $x=0$, as well, of course, but you didn't state that.