Question

Find an integer $x$ such that $0 \leq x < 527$ and $x^{37} \equiv 3 \pmod{527}$.

Answer 1

May be start by factoring 527

Answer 2

@ganeshie8 why?

Answer 3

On this site, if you use `\(` and `\)` instead of the `$` it will look like you want it to.

`Find an integer \(x\) such that \(0 \leq x < 527\) and \(x^{37} \equiv 3 \pmod{527}\).`

\(\downarrow\)

Find an integer \(x\) such that \(0 \leq x < 527\) and \(x^{37} \equiv 3 \pmod{527}\)

Answer 4

Thanks! @zzr0ck3r

Answer 5

By factoring we would know if it was a prime or not.
If it is not a prime, we can then split the congruence into a system of two simpler congruences and solve the system using CRT.

Answer 6

@ganeshie8
It's not a prime:
17* 31

Answer 7

Good. So lets split it as a system :

\(x^{37} \equiv 3 \pmod{17}\)
\(x^{37} \equiv 3 \pmod{31}\)

Answer 8

Let's solve the first congruence

\(x^{37} \equiv 3 \pmod{17}\)

Answer 9

Familiar with primitive roots ?

Answer 10

sort of..... not quite sure what to do though because usually I just combine it to make x^27 == 3 (mod 527) but instead we're trying to split it?

@ganeshie8

Answer 11

x^37*

Answer 12

Because working with 17 is easier than with 527

Answer 13

How good are you with chinese remainder theorem ?

Answer 14

You need to know below to understand my method :

1) Chinese remainder theorem
2) Euler's extension to fermat's little theorem (phi function)
3) primitive roots and theory of indices

Answer 15

We can proceed if you're familiar with them...

Answer 16

That should be fine I'm able to follow along

Answer 17

3 is a primitive of root of both 17 and 31. Let's use 3 as our base

Answer 18

\(x^{37} \equiv 3 \pmod{17} \)

using 3 as the base, above congruence implies :
\(37* \text{ind}_3 x \equiv \text{ind}_3 3 \pmod{16}\)

Answer 19

It helps to notice that the properties of "ind" are similar to "log"

Answer 20

yes i get it :)

Answer 21

\(x^{37} \equiv 3 \pmod{17} \)

using 3 as the base, above congruence implies :
\(37* \text{ind}_3 x \equiv \text{ind}_3 3 \pmod{16}\)

simplifies to
\(5* \text{ind}_3 x \equiv 1 \pmod{16}\)

Answer 22

With me so far ?

Answer 23

yup

Answer 24

Our goal is to solve "x", so let's multiply -3 both sides

Answer 25

Because -5*3 is same as 1 in mod 16

Answer 26

Ahh i see

Answer 27

so it would become ind3x≡13 (mod16)

Answer 28

Looks good

Answer 29

\(\log_3 x = 13 \implies x = 3^{13}\)

Answer 30

Reduce 3^13 in mod 17

Answer 31

http://www.wolframalpha.com/input/?i=3%5E13+mod+17

Answer 32

So \(x = 12\) ?

Answer 33

\(x^{37} \equiv 3 \pmod{17} \)

using 3 as the base, above congruence implies :
\(37* \text{ind}_3 x \equiv \text{ind}_3 3 \pmod{16}\)

simplifies to
\(5* \text{ind}_3 x \equiv 1 \pmod{16}\)

multiplying -3 both sides gives
\( \text{ind}_3 x \equiv 13 \pmod{16}\)

Since \(3^{13}\equiv 12 \pmod {17}\), the index of \(12\) relative to the primitive root \(3\) is \(13\) in modulus \(17\).

So \(x=12\) satisfies above congruence

Answer 34

it said it was incorrect.... on AoPs

Answer 35

\(x=12\) is a solution to \(x^{37} \equiv 3 \pmod{17}\)

Answer 36

You still need to solve the other congruence \(x^{37} \equiv 3 \pmod{31}\).
Then combine them both using chinese remainder theorem.

Answer 37

Oh i see... can u help me out?