# Math Help - How to solve a^x mod b = c?

1. ## How to solve a^x mod b = c?

How to solve $a^x$ $mod$ $b = c$ for $x$ minimum integer solution.

With known integers $a$, $b$, and $c$.

2. ## Re: How to solve a^x mod b = c?

If $b=1,2,4,p^\alpha,2p^\alpha$ with $\alpha\ge 1$ and $p$ an odd prime, then $b$ has a primitive root $g \mod b$.
If $(a,b)=(c,b)=1$ then $x$ind $_g a\equiv$ ind $_g c \pmod {\phi(b)}$ a linear congruence in $x$.
If $d=($ind $_g a,\phi(b))|$ ind $_g c$ then there are exactly $d$ solutions.

Then start by factoring $b$. If $b$ has a factor $2^f$ with $f\ge 3$ then solve the equation $\mod 2^f$ first.