Question

If \(p\) is a prime and \(\gcd(k, p-1)=1\), prove that the integers \[\large 1^k,2^k,3^k,\ldots,(p-1)^k \]
form a complete set of residues modulo \(p\)

Answer 1

I have googled but found nothing useful, running low on ideas at the moment... appreciate any kind of favors :)

Answer 2

basically we need to show that the integers
\[\large 1^k,2^k,3^k,\ldots,(p-1)^k\]

are congruent in some order to the integers
\[1,2,3,\ldots, (p-1)\]

in modulo \(p\)

Answer 3

Well I don't know what a residue is, it's like some kind of complex analysis thing that's also a number theory thing... But I might be able to help anyways, here goes.

If p wasn't prime, p-1 would still not share any divisors with p so it seems important or related. Specifically gcd(p, p-1)=1 is what I'm saying.

Answer 4

Ok so are you saying that gcd(5,7-1)=1 so then this means we can write 1^6, 2^6,... 5^6 and that set will be all the natural numbers less than 6?

Answer 5

Yes two consecutive integers are always relatively prime
we're given that the exponent \(k\) is relatively prime to \(p-1\)

Answer 6

small correction :

`Ok so are you saying that gcd(5,7-1)=1 so then this means we can write 1^5, 2^5,... 6^5 and that set will be all the natural numbers less than 7?`

Answer 7

Ahh I see, less than the prime itself ok.

Answer 8

Exactly!

1^5 = 1 mod 7
2^5 = 4 mod 7
3^5 = 5 mod 7
4^5 = 2 mod 7
5^5 = 3 mod 7
6^5 = 6 mod 7

we get the complete set {1, 2, 3, 4, 5, 6} as residues as desired

Answer 9

yo wassup does anyone know matlab? kind of stuck :(...ooh number theory

Answer 10

recently i remember seeing @dan815 @UnkleRhaukus @Zarkon using matlab..

Answer 11

damnnn... I need to modify a code but I'm stuck

Answer 12

I'm just trying to break it to see what happens when p-1 has a factor in common. I'm still playing around with it, kind of a weird problem to get my head around.

Answer 13

Interesting... specifically when \(k\) is a multiple of \(p-1\) we are gettomg all \(1\)'s as residues :

```
1^6 = 1 mod 7
2^6 = 1 mod 7
3^6 = 1 mod 7
4^6 = 1 mod 7
5^6 = 1 mod 7
6^6 = 1 mod 7
```

Answer 14

http://www.wolframalpha.com/input/?i=Table%5Bn%5E%286n%29+mod+7%2C+%7Bn%2C+1%2C6%7D%5D

Answer 15

Another interesting pattern,

gcd(4, 7-1) = 2

```
1^4 = 1
2^4 = 2
3^4 = 4
4^4 = 4
5^4 = 2
6^4 = 1
```
mod 7 of course. =P

Answer 16

That looks neat xD
may be we can conjecture : \(x^k\equiv a \pmod{p} \) has exactly \(d\) solutions where \(d = \gcd(k, p-1)\)

Answer 17

need to modify a bit :

If \(x^k\equiv a \pmod{p} \) has a solution, then it has exactly \(d\) solutions, where \(d = \gcd(k, p-1)\)

Answer 18

for exampile :
in your table \(x^4\equiv 2 \pmod{7}\) has \(2\) solutions : \(x=2, 5\) because \(\gcd(4, 7-1)=2\)

Answer 19

So looks like we can generalize the actual problem statement

Answer 20

i feel that can be complicated to prove compared to our original problem..

Answer 21

I found this sort of thing that's true I think for greater than 2 or 3, might be helpful or related to think about: \[\Large a^n \equiv a \mod (a(a-1))\]

Maybe the more general is easier, I don't know I really don't know much about how to think with these things haha.

Answer 22

I'm looking through my abstract algebra book for ideas lol

Answer 23

Why do we need a prime in the first place?

Answer 24

I guess it makes it so that the only possible prime p-1 can be is 2, and maybe that is a special case or something so it works by chance.

Answer 25

I'm not so sure.. maybe the author wants us to use Fermat's little thm.. but i don't see how it helps here..

Answer 26

earlier you're showing \(a^n-a\) is divisible by \(a(a-1)\) ? this looks neat, im still trying the proof xD

Answer 27

\(a^n-a = a(a^{n-1}-1) = a(a-1)(stuff)\)
nice :)

Answer 28

Yeah, I feel like I can't stop from seeing the geometric series every single day, and that was it lol.

Answer 29

\[\large \frac{a}{a} \frac{a^{n-1}-1}{a-1} = a^n+a^{n-1}+ \cdots + a+1 \equiv 1 \mod a(a-1)\]

Answer 30

i like this proof more xD

Answer 31

Honestly I had no idea there was this connection, I just figured this random thing out and never proved it but knew it had to be true cause of how I discovered it. But then what you said made me see it immediately... But it's almost so good looking that I'm not even sure if it's true lol.

Answer 32

That last step seems wrong after I put it, I just sort of assumed that all the powers of a all divided out leaving just 1. But that seems wrong since it should be 0 I think not 1.

Answer 33

At any rate, the proof by induction is simple, start here and then you can see how you could do this n times, kind of like multiplying an idempotent matrix by itself or I guess more closely related to boolean algebra. \[\large a^2 -a \equiv 0 \mod a(a-1)\]

Hmm.

Answer 34

your previous proof works with a slight modification :
\[\large \frac{a^{n}-1}{a-1} = a^{n-1}+ \cdots + a+1 \equiv 1 \pmod {a}\]

multiply \(a-1\) both sides
\[\large a^{n}-1 \equiv a-1 \pmod {a(a-1)}\]

\[\large a^{n} \equiv a \pmod {a(a-1)}\]
:D

Answer 35

I think I just repeated your argument in trying to find a better way lol. \[\large a(a^{n-1}-1) \frac{a(a-1)}{a(a-1)} \equiv a(a-1) (stuff)\]

Answer 36

lets pretend we dont know how to factor x^n-1 :P

Answer 37

Yeah we need to use fermats little theorem here I am feeling it

Answer 38

then we can prove the same using divisibility arguments alone like this :
\[a^n-a\equiv 0 \pmod {a}\tag{1}\]
\[a^n-a\equiv (a-1+1)^n-(a-1+1) \equiv (0+1)^n - (0+1) \equiv 0 \pmod {a-1}\tag{2}\]

the result follows from above two congruences

Answer 39

since a| (a^n-a) and (a-1) | (a^n-a)
we have a(a-1) | (a^n-a)

Answer 40

Oh so in the binomial expansion of (a-1) with 1 to the power n, all the terms go away except 1? Is that how you're thinking of it or is what you're saying kind of different somehow, I just have trouble with these mod things.

Answer 41

Yes... we're just expanding ( `a-1` + 1)^n using binomial thm..

Answer 42

Also, we can simply replace `a-1` by `0` because `a-1 = 0 (mod a-1)`

Answer 43

( `a-1` + 1)^n = ( `0` +1)^n (mod `a-1`)

Answer 44

Oh that's pretty simple I like that better.

Answer 45

Are you familiar with Euler's Theorem? Apparently that's what it's called lol...

Answer 46

a and m are coprime, then \[\large a^{\phi(m)} \equiv 1 \mod m\] It's a generalization of Fermat's theorem basically where \[\large \phi(m)\] is the totient function, which apparently gives the number of coprime numbers less than the number. So for primes \[\large \phi(p)=p-1\] which is how we recover Fermat's little theorem out of it. I think we can play with this to prove your thing.

Answer 47

EUler's Theorem :D

Answer 48

Yes when m is a prime, euler = fermat

Answer 49

gawd I love calculating phi, d, sigma, and meu that was the shiz.

Answer 50

lol i love sigma and tau functions xD

Answer 51

oh quick question before I go to sleep is there anything like this: \[\Large \lim_{n \to \infty} \sum_{n=1}^\infty a_n x^n \mod 2n\]

Basically a way to cut out all even numbers from a generating series or something like this as an application.

Answer 52

Wait that doesn't make sense, I'm going to bed, also what's sigma tau and mu functions?

Answer 53

I'll try this again in my evening... thanks Kai :)
\(\large \tau(n)\) : number of positive divisors of \(n\)
\(\large \sigma(n)\) : sum of those divisors

Answer 54

If it helps think of it asinfinite zeta also I remember I have proven this with nt concepts will try and send snap

Answer 55

Okk I remember it from abstract algebra as well

Answer 56

Homomorphism to something

Answer 57

Anything to do with binomial theorem?

Answer 58

What about Wilson's theorem could we use that?

Answer 59

\[\large (p-1)! \equiv -1 \mod p\] Seems related

Answer 60

p is prime ,
let p have a primitive root of \(r\le p-1~and ~gcd(r,p)=1\)
then \(1^k,...(p-1)^k\) its congruent to
\(r,r^2,r^3,.....,r^{p-1}\) in some order

Answer 61

are congruent in modulo p *
QED

Answer 62

or if i wanna use ind , let k be the smallest that satisfies
\(a\equiv r^k \mod p ,~gcd(r,p)=1\)
in other way let k be the index of a relative to r
\(ind ~a^k=k ~ind ~a \) hmm directly , right ?

Answer 63

Ahh that looks neat xD i completely forgot about primitive roots here

Answer 64

hehe im not perfectly convincing myself

Answer 65

Here I tried to complete your proof :
Let \(r\) be a primitive root of \(p\), then the given integers are congruent in some order to below integers
\[\large r^{1k},r^{2k},\ldots,r^{(p-1)k}\]

We conclude the proof by showing that none of these powers are congruent to each other. If any of these powers are congruent to each other, for \(i\ne j\):
\[r^{ik}\equiv r^{jk}\pmod{p} \]
dividing \(r^{jk}\) both sides
\[r^{ik-jk}\equiv 1\pmod{p} \]
that yields \(ik-jk \equiv 0 \pmod{p-1}\)
dividing \(k\) both sides gives \(i-j \equiv 0 \pmod{p-1}\) which is a contradiction.

That means the given set of integers(\(1^k,2^k, \ldots,(p-1)^k\)) are incongrunt to each other. Since there are exactly \(p-1\) incongruent integers, these must be congruent to \(1,2,3,\ldots,(p-1)\) in some order. \(\blacksquare\)

Answer 66

yes exactly i missed out some steps :P