Let there be two numbers $a$ and $d$ such that GCD(a,d) = 1.

For a given value of $k$, how many solutions are there for:

$$d^xk = k \mod a$$

We know that if GCD(a,k) = 1, then there is only one solution, but is there a general pattern for other values of $k$? I am particularly interested in computing $$\sum_{i=0}^{a-1} \alpha_i$$ where $\alpha_k$ is the number of solutions to $d^xk = k \mod a$.

Any insight or comments related to the problem would be great.

  • $\begingroup$ If we have $\gcd(a, k)=1$, then we take the modular inverse of $k$ from both sides to get: $$d^x \equiv 1 \pmod a$$ By Euler's totient theorem, we have the following as solutions: $$x \equiv 0 \pmod{\phi(a)} \text{ and } x \geq 0$$ This gives us an infinity number of solutions. $\endgroup$ – Noble Mushtak Jun 25 '16 at 22:03
  • $\begingroup$ Modular inverse of $k$ need not exists as $k$ may not be coprime to $a$. For example, let $d = 3$, $k= 5$ and $a = 10$. Then, for any value of $k$. Also, we would like to find the number of solutions upto equality mod $\phi(a)$, else, for all values, we will have countably infinite solutions. $\endgroup$ – Aalok Thakkar Jun 26 '16 at 6:28
  • $\begingroup$ OK, thank you for clarifying you meant equality up to $\pmod{\phi(a)}$. $\endgroup$ – Noble Mushtak Jun 26 '16 at 13:40

Let's say $m=\gcd(k, a)$ so that $k=mt$: $$d^xmt \equiv mt \pmod{\frac a m}$$ Now, $m \mid a$ and whenever we have two divisors of $a$ on both sides a modular arithmetic equation like this, there's a trick we can use to get rid of the $m$: $$d^xt \equiv t \pmod{\frac a m}$$ Now, $t$ is coprime with $\frac a m$ because otherwise, there would be some common divisor with $t \mid k$ and $\frac a m \mid a$ which would contradict that $m=\gcd(k, a)$. Therefore, multiply by the inverse of $t \pmod{\frac a m}$: $$d^x \equiv 1 \pmod{\frac a m}$$ Now, we need to solve this equation for $x$.

Now, from the Carmichael function, we know that: $$x \equiv 0 \pmod{\lambda\left(\frac{a}{m}\right)}$$ However, depending on the value of $d$, there could be more solutions than this. Also, we then need to relate $\lambda\left(\frac a m\right)$ with $\phi\left(\frac a m\right)$, which we can do with Charmichael's theorem. Once we have that, we need to relate $\phi\left(\frac a m\right)$ with $\phi(a)$, which is very hard to do without the prime factorization of $a$ and $m$.

  • $\begingroup$ Your answer has given me a number of ways to tackle the problem. Thank you. But there is a concern. Consider the case where $k=4$ and $a=10$. We have $m=\gcd(4,10)=2$, and hence $t = 2$. But $\gcd(t,a)=2≠1$, hence we do not have modular inverse for $t$. I do not see how we get $t$ and $a$ as coprime. $\endgroup$ – Aalok Thakkar Jun 27 '16 at 15:32
  • 1
    $\begingroup$ @AalokThakkar I am sorry, you are correct. However, $t$ is coprime with $\frac a m$, as I have now explained in my edited answer above. $\endgroup$ – Noble Mushtak Jun 27 '16 at 15:41
  • $\begingroup$ So yes, now it works. The number of solutions to $d^xk \equiv k \mod a$ is equal to the number of solutions to $d^x \equiv 1 \mod \frac{a}{m}$ where $m = \gcd(a,k)$. Now as you said, relating $\lambda(\frac{a}{m})$, $\phi(\frac{a}{m})$ and $\phi(a)$ is the hard part. $\endgroup$ – Aalok Thakkar Jun 27 '16 at 16:29

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.