In: Advanced Math
Let p be the prime number (2^20)*(3^7)5 + 1 = 11466178561. Solve for x such that 2^x ≡ 2376886429 (mod p) Explain your method carefully.
GIVEN DATA FROM THE PROBLEM
220 * 37 * 5 + 1 = 11466178561
2^x ≡ 2376886429 (mod p)
SOLVING FOR X :
AS WE HAVE
is a prime number so it is odd as bevause if then the system has no solution as we have the theorem has a solution if and only if divides .
So is odd and so is even and so .
Now ,
, as .
where .
Hence the required solution of the given congruence are given by ,