Question

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

Answer 1

Answer:

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

Step-by-step 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)$