Finding modulo inverse if gcd is not 1

Question

I have to find (p^e-1)/(p-1) mod 1000000007, where p is a prime number. if gcd(p-1,1000000007) is not 1, then the modular inverse of (p-1) is not defined. Also, (p^e-1) is divisible by (p-1) (sum of a Geometric Progression). Also I can't find (p^e-1) since p,e<=10^18. So how do I find (p^e-1)/(p-1) mod 1000000007

Answer 1

When you're dividing integers, and then taking the modulus, you have to treat the prime factors of the modulus in a special manner. Consider for example 6/3 mod 3. If we just tried to write 6/3 mod 3 = (6 mod 3)/(3 mod 3) we would have undefined 0/0, whereas the correct answer is of course 6/3 mod 3 = 2 mod 3 = 2.

So what we need to do is to factor powers of 3 out of both the numerator and denominator, and divide those separately (by subtracting exponents). So we have 6 = 3^1 x 2, 3 = 3^1 x 1, so 6/3 = 3^1/3^1 x 2/1 = 3^{1-1} x 2 = 3^0 x 2 = 2 mod 3. Let's try a more complicated example: 18/6 mod 3 = (3^2 x 2)/(3^1 x 2) = 3^{2-1} x 2/2 = 3 x 1 = 3 mod 3 = 0.

Here's another example: 36/18 = (3^2 x 4)/(3^2 x 2) = 3^{2-2} x 4 x 2^{-1} mod 3 = 4 x 2 mod 3 (since 2^{-1} = 2 mod 3) = 8 mod 3 = 2. In general, we subtract exponents of the power of 3 part, and invert mod 3 the non-power of 3 part of the divisor.

In your example, we have to find the highest power m of 1000000007 that goes into p^e-1, and rewrite p^e-1 = 1000000007^m x s, where s is relatively prime to 1000000007. We do the same for p-1 = 1000000007^n x t, where t is relatively prime to 1000000007. Then the quotient (p^e-1)/(p-1) = 1000000007^{m-n} x s x t^{-1}. The answer is 0 mod 1000000007 if m>n; otherwise the answer is s x t^{-1} mod 1000000007. The inverse of t mod 1000000007 exists because t is relatively prime to 1000000007; the inverse can be calculated by a modified version of the Euclidean algorithm.

Answer 2

Since 1000000007 is prime, there are two cases.

Case 1: 1000000007 is a factor of p-1. Then p mod 1000000007 = 1, so 1+p+p^2+...+p^(e-1) = 1+1+1...+1 = e mod 1000000007.

Case 2: 1000000007 is relatively prime to p-1 and you can compute 1/(p-1) as (p-1)^1000000005 mod 1000000007, or by using Euclid's algorithm, and you can compute powers mod 1000000007 relatively rapidly using exponentiation by squaring.

Answer 3

You have two cases

1. p-1 is coprime to the large prime 1000000007. This is always true for p <= 1000000007 and usually true for larger p. It seems you know what to do in this case - use an algorithm to find the modular inverse of p-1, i.e. a such that a * (p - 1) == 1 mod 1000000007.

2. p-1 is a multiple of 1000000007 - i.e. p-1 == k*1000000007. In this case, p == k*1000000007 + 1

   Let us turn our attention to the top line of the expression

   p^e - 1 == (k * 1000000007 + 1) ^ e - 1
   

   This can be expanded by the binomial expansion as

   ((k*1000000007)^e + e*(k*1000000007)^(e-1) + ... + 1) - 1
   

   Remember, though, that (k*1000000007) == p-1. So, the expansion is

   ((p-1)^e + e*(p-1)^(e-1) + ... + e*(p-1))
   

   We can divide through this by p-1 and are left with

   ((p-1)^(e-2) + e*(p-1)^(e-2) + .... + e)
   

   We know that all the terms containing p-1 are 0 mod 1000000007 in this case, so we are simply left with the last term, e. Thus, in this case, the result of the expression (p^e - 1) / (p - 1) mod 1000000007 is e - you do not find the modular inverse of p-1 because you can't, but neither do you need to.

Answer 4

1000000007 is a prime number, so if p-1 < 1000000007 the gcd will always be 1. If p-1 is some multiple of 1000000007 then by definition it is zero modulo 1000000007 and so there is no inverse defined .