Here's the proof what's the question!

**Deadstar** · April 26th 2010, 09:19 AM

This is a 4 part question on my tutorial and if you prove part d) the rest follow, except there's no part d) in the question! I can prove a), b) and c) without using whatever d) is but just thought I'd see if you guys know what this proof is actually proving!

Q. Let p be an odd prime, and a, b be integers not divisible by p. Prove that
a) a \equiv b (mod p) implies that $\bigg{(}\frac{a}{p} \bigg{)} = \bigg{(}\frac{b}{p} \bigg{)}$

b) $\bigg{(}\frac{ab}{p} \bigg{)} = \bigg{(}\frac{a}{p} \bigg{)}\bigg{(}\frac{a}{p} \bigg{)}$ .

c) $\bigg{(}\frac{a^2}{p} \bigg{)}=1$ ; $\bigg{(}\frac{a^2b}{p} \bigg{)} = \bigg{(}\frac{b}{p} \bigg{)}$ .

(I though perhaps part d) was the second equality in part c) but I don't think the proof matches up.

PROOF.

a), b) and c) follow from d) so we should prove that first!
d) Take a primitive root g, with $a \equiv g^k$ mod $p$ .

Then $a^{\tfrac{p-1}{2}} = g^{\tfrac{(p-1)k}{2}}$ .

As $g^{\tfrac{(p-1)}{2}} \equiv -1$ mod $p$ we see that...

$g^{\tfrac{(p-1)k}{2}} \equiv 1$ mod $p$ if $k$ is even (i.e if a is a quadratic residue),

while $g^{\tfrac{(p-1)k}{2}} \equiv -1$ mod $p$ if $k$ is odd (i.e a non quadratic residue). Hence result.

I was thinking it was probably something like show that if g is a primitive root and k is even then,

$\bigg{(}\frac{g^k}{p} \bigg{)} = 1$ . and if k is odd then ... = -1.

**chiph588@** · April 26th 2010, 11:56 AM

Here's part a. The rest follow in a similar fashion.

$a\equiv b\bmod{p} \implies a^{(p-1)/2}\equiv b^{(p-1)/2}\bmod{p} \implies \left(\frac ap\right) = \left(\frac bp\right)$

**Deadstar** · April 26th 2010, 12:10 PM

Originally Posted by chiph588@

Here's part a. The rest follow in a similar fashion.

$a\equiv b\bmod{p} \implies a^{(p-1)/2}\equiv b^{(p-1)/2}\bmod{p} \implies \left(\frac ap\right) = \left(\frac bp\right)$

Lol I think you misread the question...

I can prove a), b) and c) fine. My question was about this mystery part d) that only has a proof but the actual question was not on the tutorial.
Basically, I've been given the proof, can you work out what the question was? My lecturers away so I can't ask him right now.

I only included a,b and c so folk can see the whole question and what part d would imply.

**chiph588@** · April 26th 2010, 12:25 PM

Originally Posted by Deadstar

Lol I think you misread the question...

I can prove a), b) and c) fine. My question was about this mystery part d) that only has a proof but the actual question was not on the tutorial.
Basically, I've been given the proof, can you work out what the question was? My lecturers away so I can't ask him right now.

I only included a,b and c so folk can see the whole question and what part d would imply.

Probably too hard to deduce part d.

**Deadstar** · April 26th 2010, 12:28 PM

Originally Posted by chiph588@

Probably too hard to deduce part d.

Ah well thought I'd post it up to see...

Thread: Here's the proof what's the question!

LinkBack

Thread Tools

Display

Here's the proof what's the question!

Similar Math Help Forum Discussions

Somehow different question about a proof

proof question 5

a proof question..

a proof question..

Proof question

Search Tags