# Solving for exponent in modular arithmetic equation

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.

• 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. – Noble Mushtak Jun 25 '16 at 22:03
• 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. – Aalok Thakkar Jun 26 '16 at 6:28
• OK, thank you for clarifying you meant equality up to $\pmod{\phi(a)}$. – 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$.
• 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. – Aalok Thakkar Jun 27 '16 at 15:32
• @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. – Noble Mushtak Jun 27 '16 at 15:41
• 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. – Aalok Thakkar Jun 27 '16 at 16:29