Could anyone give me a hint how to calculate (a ^ b) % c (with 2 <= a < 10^1000000, 1 <= b < 10^1000000, 2 <= c <= 10^9)? I try to use this formula (a ^ b) % c = ((a % c) ^ (b % phi(c)) % c (phi(c) is Euler's totient). But I realize that a and c aren't coprime. Is it necessary that a and c must be coprime? Or we must use other formula. Thank you! ^^ asked 05 Nov '14, 09:18

You can learn CRT mostly from it's wikipedia article. Break General modulo into prime power modulo's This can be done by write n in its prime representation n = p_{1}^{q1}. . . p_{k}^{qk} Compute modulo p^k by usual methods Merge those answers Short Example Details of Merging Similarly define alpha2 So basically find alpha1, alpha2. For finding these, you need to solve two equations of two variables. That can be done by simplifying the equations written above. Finally your answer will x1 * alpha1 + x2 * alpha2. Sample Implementation answered 05 Nov '14, 10:14
sir can you please explain the constructive algorithm of CRT...I am unable to get it from the example given in wiki link..thank you in advance
(05 Nov '14, 14:15)
1
Ohk, its not that hard actually. It can be derived easily. I am writing the derivation in the modified answer.
(05 Nov '14, 16:13)
That is very nice method. This is the first time I've read it. Thank you very much! :D
(05 Nov '14, 20:39)
My friend! I have a question. If a and c aren't coprime, it means that there is a prime (let it is pi) that a % pi == 0 && c % pi == 0, and pi is in the set of prime (we break c), and when we apply above formula, we can't calculate value of ((a % pi) ^ (b % phi(pi))) % pi (because gcd(a, pi) > 1) (after calculate, we can use CRT to calculate the answer). Could you tell me more about that? Thank you in advance :D
(06 Nov '14, 16:42)
1
if a % p = 0, then a^n % p will always be zero.
(07 Nov '14, 19:08)
Oh :D, thank you :D
(08 Nov '14, 08:50)
showing 5 of 6
show all

Use logarithmic exponentiation Here is the c++ implimentation int power(int a,int b){ long long x=1; while(b){ if(b&1){ x=a; x%=mod; } a=a; a%=mod; b>>=1; } return x; } answered 06 Nov '14, 22:01

Hi, just check 《Introduction to Algorithms, 3rd Edition》Chapter 31.6. Especially "Raising to powers with repeated squaring" section In order to calculate a^b(mod n):
answered 09 Sep '18, 03:48

Can you provide a link to the problem?
The language for above problem is Vietnamese, do you want to get the link?