Needed help in modular arithmatic for finding (a^(n!))%m

general
,
1

Please suggest how to find (a^(n!))%m where a<=10^10 and n<=10^3 and m is prime.
Also suggest some good resources and problems to learn all such concepts in modular arithmatic.
Thanks in adv!.

2

Is m prime?
Then we know that a^{p-1} \equiv 1 \pmod p (Fermat’s little theorem)

Since
n! = \big\lfloor \frac{n!}{p-1} \big\rfloor * p-1 + n! \pmod {p-1} and
a^{x+y} = a^x * a^y and
a*b \pmod {m} = (a \pmod m * b \pmod m) \pmod m

we can conclude that a^{n!} \equiv a^{n! \pmod {p-1}} \pmod p

You can precompute values of n! \pmod {p-1} in \theta(\text{MAXN})
a^n \pmod p can be computed in \theta(\log n) using modular exponentiation

PS: if m in not prime then we can use Euler’s theorem

7 Likes
3

Can you please elaborate your conclusion a^(p−1)≡1(mod p) then a^(n!)≡a^(n!)(modp−1)(modp).I wanted to learn how can we arrive at this result from the starting.

4

updated the answer

5

@nilesh3105 I think you complicated the problem and idea. I have a very simple solution:

Observe that a^{n!} is simply a^{1*2*3*4*...*n}. It’s a standard idea (7th class maths) that a^{n*m} is simply (a^{n})^m.
So the code is as simple as this:

long long res = a;
for(int i = 1; i <= n; ++i){ //as n is atmost 1000, we can just iterate over it.
   res = power(res, i, mod); // modulo exponentiation.
}
//Now res is your final answer.

Problem for practice: https://code.google.com/codejam/contest/3254486/dashboard#s=p0

2 Likes
6

Unfortunately, your idea fails with this test: Consider a as 2, n as 1 and mod as 2. According to your logic and since mod is prime, the answer is 2^{1 \% (2 - 1))} \% 2 which is 1. But the actual answer is 0.

7

@nilesh3105 is not completely wrong, he has just missed a point. Fermat’s little theorem holds when a is not a multiple of p. When it is, the solution can be found trivially.

2 Likes
8

Yeah you are right I forgot to mention the edge case

9

@achaitanyasai kindly refer to problem LARGE POWER on codechef peer section.
Your solution won’t pass the time limit with given constraints.

1 Like
10

Thanks for your kind suggestion. I kindly referred to your problem. And I think if you have kindly mentioned about test cases in the above question, I would have kindly skipped answering it. As there was no mention about test cases, I kindly thought that the above answer is a bit complicated and kindly answered a stupid answer with codejam in mind.

And finally I am sorry for my stupid answer!!!

1 Like