Find $a$ such that $83359654581 ... 10843035531 ^ a \equiv 1 \pmod{32003240081}$

Question

Find $a$ such that

$83359654581036155008716649031639683153293510843035531 ^ a \equiv 1 \pmod{32003240081}$

I am quite familiar with sort of equation like find m such that m^d = c (mod n), but I think it don't help me in this problem since it relative exponent.

I have read this, but in my problem, the number is so big.

Answer 1

Let $n = 83359654581036155008716649031639683153293510843035531$.
Let $m = 32003240081$. It has the prime factorization $m = pq$ where $p = 160009, q = 200009$.
One can verify $\gcd(n,p) = \gcd(n,q) = 1$. By Fermat's little theorem, we have

$$ \begin{cases} n^{p-1} \equiv 1 \pmod p\\ n^{q-1} \equiv 1 \pmod q \end{cases} \quad\implies\quad \begin{cases} n^\ell \equiv 1 \pmod p\\ n^\ell \equiv 1 \pmod q \end{cases} \quad\text{ where }\quad \ell = {\tt lcm}(p-1,q-1) $$ Together with Chinese Remainder theorem, this leads to $$n^\ell \equiv 1 \pmod {pq}$$ Since we only want an $a$, not the smallest one, $\ell = {\tt lcm}(p-1,q-1) = 4000360008$ is a solution.

Answer 2

Suppose $n$ and $k$ are relatively prime. Then $n^{\varphi(k)}\equiv 1 \bmod k$. The same is true if we change $\varphi(k)$ for any multiple of $\varphi(k)$. For example $k!$.

We therefore have that $n^{k!}\equiv 1 \bmod k$ whenever $k$ and $n$ are relatively prime.

So all you have to do is check that those numbers are relatively prime, you can do that really fast with the euclidean algorithm (on a computer of course).