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 ,