You are Here: Home >< Maths

# kth powers in Z_p* Watch

1. I've really thought about this but I can't seem to get to the required result. Any help on what to do is much appreciated.

Thanks.
2. (Original post by Peter8837)

I've really thought about this but I can't seem to get to the required result. Any help on what to do is much appreciated.
If you're still working on this, the "x = y^k implies x^{(p-1)/d} = 1" is fairly easy by Fermat's Little Theorem, and part 2 follows quickly from part 1 by setting k=437, p=1013, and working out the HCF. Simple trick to simplify the HCF if you didn't spot it: hcf(1012, 437) = hcf(253, 437) by cancelling the spare factor of 4; = hcf(253, 184) because 437-253 = 184; = hcf(253, 23) by cancelling the spare factor of 8; and this is clearly 23. It's a bit faster than Euclid, to incorporate some very simple prime factor decomposition.
Not quite sure about how to do "x^{(p-1)/d} = 1 implies x is a kth power"; I'll have another think.
3. For the other direction you need to write x=g^y were g generates the group. then p-1|(p-1)*y/d =>d|y.

Also k=d*l where l coprime to p-1.

By Euclidean Algorithm there is a so that a*l=1mod(p-1)

I put the full solution in white.

y*a*l=ymod(p-1)

g^(y*a*l)=g^y=x

also y*l=k*b

Now y*a*l=a*b*k

taking h=g^(a*b)

h^k=x

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: June 2, 2013
Today on TSR

...in schools

### I think I'm transgender AMA

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.