0

This is probably a very basic question, but beeing new to modular arithmetic it's difficult to to search for an answer without knowing a name for the concept. So for given $a$ and $n$:

$$a * x \equiv a \pmod n$$

  • Is there a name for such $x$?
  • Is there an efficient method to find the smallest $x > 1$?
  • Is there an efficient method to find many such $x$?
Niklas
  • 488

2 Answers2

1

There are $a>0$ and $x>1$ such that $a x \equiv a \bmod n$ iff $n$ is composite.
Indeed, if $n=uv$ with $u,v>1$, then take $a=u$, $x=v+1$.

If $a$ is fixed, then the smallest $x>1$ is such that $a(x-1)=lcm(a,n)=\dfrac{an}{\gcd(a,n)}$.
Therefore, $x=1+\dfrac{n}{\gcd(a,n)}$.

There is no standard name for such $x$. You might call it a multiplicative identity for $a$.

lhf
  • 216,483
0

If you mean that $a\cdot{}x\equiv{}a(n), \forall{}a$ then the name for such an $x$ is the "multiplicative identity", and so $x\equiv{}1(n)$. Moreover, any other such value $y$ for which $a\cdot{}y\equiv{}a(n)$ has the quality $y\equiv{}1(n)$.

Thus, to answer your second question, the smallest such $x$ is always $1$.

For your third question, any value $y$ for which $y=r\cdot{}n+1$, where $r\in{}\mathbb{Z}$, will satisfy $y\equiv{}1(n)$.

If, however, you are just interested in $a\cdot{}x\equiv{}a(n)$ for a specific $a$, then it boils down to being able to find an $x$ such that $a(x-1)$ is a multiple of $n$. (Note that $x=1$ satisfies that trivially.)