Question

HELP! primitive roots
http://prntscr.com/4lfo9d

Answer 1

i don't get these :(

Answer 2

(a) Note that \((a^k)^h=a^{kh}\)

Answer 3

\[\large a^{hk}\equiv 1 \mod n\]

\[\large \left(a^{h}\right)^k\equiv 1 \mod n\]

nice :)

Answer 4

(b) There is only one such number such that \(a^2\equiv1\) modulo a prime and \(a\not \equiv 1\).

Answer 5

(c) Assume otherwise. Then?

Answer 6

im still in (b), one sec

Answer 7

i was never good with quadratic congruences

Answer 8

\(\large a^{2k}\equiv 1 \pmod p\)

Answer 9

\(\large \left(a^{k}\right)^2\equiv 1 \pmod p\)

Answer 10

So far so good.

Answer 11

why a^k cannot be 1 ?

Answer 12

i mean, why a^k cannot be 1 mod p ?

Answer 13

Because if it was, then what would the order be?

Answer 14

it could be 1 or -1, right ?

Answer 15

You should probably ask the question why it shouldn't be anything BUT -1 or 1.

Answer 16

a^k has to be of form \(\large pq \pm 1\) i think

Answer 17

but its same as \(\pm 1\) in \(\large \mod p\)

Answer 18

Yes, but why?

Answer 19

because p | pq ?

Answer 20

I'm not sure where the statement \(pq \pm 1\) is coming from. Did you prove that already?

Answer 21

im not sure i answer ur question, im not sure myself haha! idk if there is a clean way to explain this

Answer 22

\(\large x^2 \equiv 1 \mod p\)

Answer 23

All right. Perfect.

Answer 24

we're solving \(\large x\)

Answer 25

Yep, now the question is why couldn't it be 1?

Answer 26

If \(a^k\equiv 1\), what would be the order of \(a\), then?

Answer 27

x can be 1 or -1,
both satisfy x^2 = 1 mod p

Answer 28

Oh wait, you're asking about order

Answer 29

order of a will be k ?

Answer 30

but we're given that order of a is 2k, impossible so discard -1
got it got it :)

Answer 31

Right, but we said that the order is \(2k\), so that contradicts our statement, thus \(a^k\equiv -1\).

Answer 32

Exactly.

Answer 33

thank you :)
i see c is right, but just wondering if there a neat way to phrase the argument

Answer 34

if the order is not n-1,
then there exists some divisor less than n making n a composite

this will do ?

Answer 35

That seems like a difficult statement to prove. I would go for, if \(n\) is not prime then its order must be less than \(n-1\).

Answer 36

Of course, in this case I am assuming Euler's theorem, so that's bad.

Answer 37

I'm also going to sleep since it is 4:33 AM here... and I'm still up.

Answer 38

Oh, wait, no, you need a really weak version of Euler's which is just for primes, but it's pretty clear.

Answer 39

So, go for it, try it out.

Answer 40

remember that pi(n) for composite number <n-1

Answer 41

go out and watch the night sky, at ~4am it looks so beautiful !!
thanks for all the help, have good sleep :)))

Answer 42

any order is <=n-1 as well
thus n has to be prime is order =n-1

Answer 43

got the idea, il put some words and manage this thanks !