Question

Solve the congruence x^329 = 452 (mod 1147). [Hint. 1147 is not prime.]

Answer 1

The answer is
`x \equiv 763 \:(mod \: 1147)`

Explanation:

The following steps will give a solution to the congruence

`x^(329) \equiv 452 \:(mod \:1147)`

1. Compute Euler's Phi function
`\phi(1147)`.

We have
`1147=31\cdot 37` by prime factorization, so that
`\phi(1147)=\phi(31)\cdot \phi(37)=30\cdot 36= 1080`

because
`\phi(p) =p-1` where p is a prime number.

2. Find positive integers u and v that satisfy
`329\cdot u-\phi(1147)\cdot v=1`.

We know a solution exists, since
`gcd(329,1080)=1`, using the Euclidean algorithm allows us to find the solution
`1 = -151\cdot 329 + 46\cdot 1080`

In order to get positive values for u and v, we modify this solution:

`u=-151+1080=929` and
`v=-46+329=283`

The equation

`329 \cdot 929-1080\cdot 283=1`

provides the key to solving the original problem.

3. Compute
`b^u \:(mod \:m)` by successive squaring. The value obtained gives the solution x.

We have
`452^(929)\:(mod \: 1147)`, so
`x \equiv 452^(929)\:(mod \: 1147)`

To use this method start by looking at the exponent 929 and represent it as a sum of powers of 2 this is called the binary expansion of 929. To do this, find the largest power of 2 less than your exponent in this case it’s
`2^9=512`. Subtract 512 from 929 getting 417. And continue in this manner to get:

`929=2^9+2^8+2^7+2^5+2^0`

Now

`452^(929)\:(mod \: 1147)=452^(2^9+2^8+2^7+2^5+2^0)\:(mod \: 1147)`

So all you have to do is to calculate the numbers

`452^(2^9) \:(mod \:1147),452^(2^8) \:(mod \:1147),452^(2^7) \:(mod \:1147),452^(2^5) \:(mod \:1147), 452^(2^0) \:(mod \:1147)`

and multiply them together, then take the product
`(mod \: 1147)`

`452^(2^9) \:(mod \:1147)=417\\452^(2^8) \:(mod \:1147)=359\\452^(2^7) \:(mod \:1147)=565\\452^(2^5) \:(mod \:1147)=417\\452^(2^0) \:(mod \:1147)=452`

`x \equiv 452^(929)\:(mod \: 1147)\\x \equiv 417 \cdot 359\cdot 565 \cdot 417\cdot 452 \:(mod \: 1147)\\x \equiv 121\cdot 376 \:(mod \: 1147)\\x \equiv 763 \:(mod \: 1147)`