Cryptography problem involving prime numbers

[docnet]

Homework Statement

I'm having trouble solving this problem. any help would be appreciated.

Relevant Equations

p = 3(mod4)
x^2 = -1(modp)

Here is my attempt

When we raise both sides to the power (p-1)/2, we get
x^(p-1)= -1^[(p-1)/2](modp)

Looking at p=3(mod4), the possible values of p are
{3, 7, 11, 19, 23, 31...}.

Putting these values of p into (p-1)/2 we get odd integers.
{1, 3, 5, 9, 11, 15...}.

So we have
x^(p-1) = -1(modp)

We let p = 3 then we have
(x)^2 = -1(mod3)

which is equivalent to
x^2=3k -1

With the solutions
x= {sqrt(2), sqrt(5), sqrt(8), ...}

The solutions are not integers, which are undefined for the modulo operation. therefore x^2=-1(modp) have no solutions.

This is the wrong answer. I don't know

 

[Office_Shredder]

It doesn't seem like you've tried using Fermat's little theorem yet.

 

[docnet]

Im struggling to see how to incorporate the information from FLT into the problem.

 

[docnet]

Can a moderator move this thread into the right subforum? Sorry, I should have posted this in the “calculus and beyond.“ section. Thanks

 

[pasmith]

Homework Statement:: I'm having trouble solving this problem. any help would be appreciated.
Relevant Equations:: p = 3(mod4)
x^2 = -1(modp)

View attachment 269850

Here is my attempt

When we raise both sides to the power (p-1)/2, we get
x^(p-1)= -1^[(p-1)/2](modp)

Looking at p=3(mod4), the possible values of p are
{3, 7, 11, 19, 23, 31...}.

Putting these values of p into (p-1)/2 we get odd integers.
{1, 3, 5, 9, 11, 15...}.

So we have
x^(p-1) = -1(modp)

It would have been better to get here by setting p = 4k + 3 so that <br /> \frac{p - 1}{2} = \frac{4k + 2}{2} = 2k + 1 and hence (-1)^{(p-1)/2} = -1.

 

[pasmith]

Im struggling to see how to incorporate the information from FLT into the problem.
View attachment 269890

You just need to substitute x^{p-1} \equiv 1 \mod p in <br /> x^{p-1} = -1 \mod p and draw the appropriate conclusion.