# Fermat and Chinese Remainder

• If the modulus weren't 1337 = 7 * 191 but a prime number p, we could use Fermat's little theorem to first reduce the exponent to e = b % (p-1) and then compute the result as ae % p. Oh well, we can do it for 1337's prime factors 7 and 191 and then combine the two results with the Chinese remainder theorem. I'll show my derivation of the magic constants 764 and 574 after the solutions below.

I got the solution using Fermat from @Stomach_ache (thanks) and only added the Chinese remainder theorem stuff to adapt it to non-primes like 1337.

## Solution 1: Python "golf"

The helper computes ab modulo the prime `p`.

``````def superPow(self, a, b):
def mod(p):
return pow(a, reduce(lambda e, d: (10*e + d) % (p-1), b, 0), p) if a%p else 0
return (764 * mod(7) + 574 * mod(191)) % 1337
``````

## Solution 2: C++

The helper computes ab modulo the given prime.

``````int superPow(int a, vector<int>& b) {
return (764 * superPow(a, b, 7) + 574 * superPow(a, b, 191)) % 1337;
}

int superPow(int a, vector<int>& b, int prime) {
if (!(a %= prime)) return 0;
int e = 0, mod = prime - 1;
for (int digit : b)
e = (e * 10 + digit) % mod;
int pow = 1;
while (e) {
if (e & 1)
pow = pow * a % prime;
a = a * a % prime;
e >>= 1;
}
return pow;
}
``````

## Using the Chinese Remainder Theorem

Let's call x = ab. We want to know x % 1337. The helper function using Fermat already gave us u and w so that x % 7 = u and x % 191 = w. Or put differently, x ≡ u (mod 7) and x = w + 191t for some integer t. Combine these to get w + 191t ≡ u (mod 7). Subtracting w and multiplying with [191-1]7 (the multiplicative inverse of 191 modulo 7) we get t ≡ (u-w)·[191-1]7 (mod 7).

We have [191-1]7 = [(191%7)-1]7 = [2-1]7 and one can easily see that the latter is 4, as (2*4)%7=1.

Using that, we have t ≡ 4(u-w) (mod 7) or in other words t = 4(u-w) + 7s for some integer s. Which means:

x = w + 191t
= w + 191(4(u-w) + 7s)
= 764u - 763w + 1337s
= 764u + (1337-763)w + 1337(s-w)
= 764u + 574w + 1337(s-w)

So we can compute x from u and v as x = (764u + 574w) % 1337, like I have done in my solutions.

• I like this solution: use Fermat's little theorem to set up Chinese Remainder theorem equations. A very representative/general method. However, it might not be the best for this question, because it happens to be the case that 1337 only has two prime factors.

• @StefanPochmann great job Stefan. You reminded me of when I studied this stuff in network security (RSA, etc) class :-)

• If the modulus weren't 1337 = 7 * 191 but a prime number p, we could use Fermat's little theorem to first reduce the exponent to e = b % (p-1) and then compute the result as ae % p.

Here's the proof of what Stefan is saying, for whom is interested in this stuff: http://math.stackexchange.com/questions/379996/computing-bmods-with-large-exponents-by-paper-and-pencil-using-fermats-littl

• this more like a 'back substitution' method rather than Chinese Remainder, anyway, it's such a brilliant approach, I like it very much.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.