The Carmichael's function says that for $a\in \mathbb{Z}_n^*$, if $gcd(a,n)=1$, then \begin{equation} a^{\lambda(n)} \equiv 1 \;(mod\; n). \end{equation} My aim is to find $a$ if factorization of $n$ is known? Since it is a polynomial equation of degee $\lambda(n)$, so it has $\lambda(n)$ solution. Suppose any how we are able to find all solution of the equation, how can we find the exact $a$? Can any one help me to proceed further?

  • 1
    $\begingroup$ What do you mean with find $a?$. All $a\in \mathbb{Z}_n^*$ are solutions, i.e. there are $\phi(n)$ solutions. $\endgroup$ – gammatester Jun 8 '16 at 8:15
  • 2
    $\begingroup$ "Since it is a polynomial equation of degee λ(n), so it has λ(n) solution" No, it does not, because 1) $\mathbf{Z}_n$ is not an integral domain; and 2) there may be repeated roots. $\endgroup$ – fkraiem Jun 8 '16 at 9:18

If you are only given $a^{\lambda(n)} = 1$, then it is obviously impossible to recover $a$, since this is true for all $a$. To take a simpler example, say I tell you that the square of a number is $4$, and ask you to find what the number is. This is impossible, because you are not given enough information to tell whether the number is $2$ or $-2$.

| improve this answer | |
  • $\begingroup$ An example closer to the OP's question: Find $a$ given $a^0=1$. $\endgroup$ – CodesInChaos Jun 8 '16 at 10:28
  • $\begingroup$ Suppose I have a relation $D=r^{2\lambda(n)}\; mod\;n$, where $D$ and factorization of $n$ is known and $r$ is chosen randomly from $QR_n$, the group of quadratic residues modulo $n$ and it is unknown. How to find this particular $r$? Is the above relation holds if and only if $D=1$? $\endgroup$ – Pinkimani Goswami Jun 8 '16 at 11:27
  • $\begingroup$ @PinkimaniGoswami You have been told that $a^{\lambda(n)} \equiv 1 \pmod n$ for all $a \in \mathbf{Z}_n^*$; there is nothing more to say. You seem very weak in elementary number theory, so I suggest you study it seriously. $\endgroup$ – fkraiem Jun 9 '16 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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