Function Posted May 2, 2014 Share Posted May 2, 2014 hello everyone Let me get straight to the point: [math]p[/math] is prime, [math]a\in\mathbb{N}[/math], [math]p\nmid a[/math]; [math]A=\{a,2a,3a,\cdots ,(p-1)a\}[/math] Let [math]ra\equiv sa\pmod{p}[/math] Then: [math]ra=mp+R[/math] and [math]sa=np+R[/math] [math](r-s)a=(m-n)p[/math] So [math]p\mid (r-s)[/math] So [math]r\equiv s\pmod{p}[/math] The elements of [math]A[/math] must thus all be different and congruent with the elements of the set [math]B=\{1,2,3,\cdots ,(p-1)\}[/math]. The sequence is not important. I found these steps of the proof (which continues after this) on the internet, and I don't really get the statement I put bold... Can someone explain this to me? Thanks! Function Link to comment Share on other sites More sharing options...

Acme Posted May 2, 2014 Share Posted May 2, 2014 hello everyone Let me get straight to the point: [math]p[/math] is prime, [math]a\in\mathbb{N}[/math], [math]p\nmid a[/math]; [math]A=\{a,2a,3a,\cdots ,(p-1)a\}[/math] Let [math]ra\equiv sa\pmod{p}[/math] Then: [math]ra=mp+R[/math] and [math]sa=np+R[/math] [math](r-s)a=(m-n)p[/math] So [math]p\mid (r-s)[/math] So [math]r\equiv s\pmod{p}[/math] The elements of [math]A[/math] must thus all be different and congruent with the elements of the set [math]B=\{1,2,3,\cdots ,(p-1)\}[/math]. The sequence is not important. I found these steps of the proof (which continues after this) on the internet, and I don't really get the statement I put bold... Can someone explain this to me? Thanks! Function Off the cuff I think it just means that it doesn't matter in what order you choose test cases. For example, you could let p=7 and let a=2 first, even though 7 is not the first prime and 2 is not the first a. Link to comment Share on other sites More sharing options...

Function Posted May 2, 2014 Author Share Posted May 2, 2014 Off the cuff I think it just means that it doesn't matter in what order you choose test cases. For example, you could let p=7 and let a=2 first, even though 7 is not the first prime and 2 is not the first a. what about the congruency of elements of A to those of B? Link to comment Share on other sites More sharing options...

Acme Posted May 2, 2014 Share Posted May 2, 2014 what about the congruency of elements of A to those of B? It's awkward wording, but I think B just shows that the a's are Natural numbers. Link to comment Share on other sites More sharing options...

Function Posted May 2, 2014 Author Share Posted May 2, 2014 It's awkward wording, but I think B just shows that the a's are Natural numbers. In an explanation of the proof, it says: division of elements of A and division of elements of B by p, will result in equal remainders... Link to comment Share on other sites More sharing options...

Acme Posted May 2, 2014 Share Posted May 2, 2014 In an explanation of the proof, it says: division of elements of A and division of elements of B by p, will result in equal remainders... Hmmmmmm...while we wait to see if others respond, can you link to the page you are reading from? Link to comment Share on other sites More sharing options...

John Posted May 2, 2014 Share Posted May 2, 2014 It may just be noting that, given our a and p, the first p - 1 positive multiples of a will, mod p, give us the first p - 1 natural numbers, though not necessarily in order. As an example, consider a = 8 and p = 5. Then the first p - 1 = 4 multiples of a are 8, 16, 24 and 32. These are congruent (mod 5) to 3, 1, 4 and 2, respectively. 2 Link to comment Share on other sites More sharing options...

Function Posted May 2, 2014 Author Share Posted May 2, 2014 It may just be noting that, given our a and p, the first p - 1 positive multiples of a will, mod p, give us the first p - 1 natural numbers, though not necessarily in order. As an example, consider a = 8 and p = 5. Then the first p - 1 = 4 multiples of a are 8, 16, 24 and 32. These are congruent (mod 5) to 3, 1, 4 and 2, respectively. Now that, seems very plausible. Thanks, John! Link to comment Share on other sites More sharing options...

Someguy1 Posted May 3, 2014 Share Posted May 3, 2014 (edited) Let's unpack this a little by annotating as we go. p is prime, [latex]a\in\mathbb{N}, p\nmid a[/latex] Let [latex]A=\{a,2a,3a,\cdots ,(p-1)a\}[/latex] Now, we want to show that these p-1 numbers in A are all the nonzero residues mod p. In other words, no two of these are equal mod p. So, assume that two of them are equal. Let [latex]ra\equiv sa\pmod{p}[/latex] with [latex] 1 \leq r, s \leq p-1[/latex] Then: ra=mp+R and sa=np+R What is R? This is a little messy. I think I would just skip that line entirely since there's an easier way to go. Note that if [latex]ra\equiv sa\pmod{p}[/latex] then [latex]p |(ra - sa) = (r - s) a[/latex] Then you can apply the theorem that [latex]p \mid ab[/latex] implies that either [latex]p \mid a[/latex] or [latex]p \mid b[/latex], plus the fact that [latex]p \nmid a[/latex] to conclude that [latex]p | (r - s)[/latex] So [latex]r\equiv s\pmod{p}[/latex] But r and s are between 1 and p - 1, so the only way they can be equivalent mod p is if r = s. In other words, the set A contains a complete set of nonzero residues mod p in some order. That's what they mean by: The elements of A must thus all be different and congruent with the elements of the set [latex]B=\{1,2,3,\cdots ,(p-1)\}[/latex]. The sequence is not important. And now tell us the rest Edited May 3, 2014 by Someguy1 Link to comment Share on other sites More sharing options...

Function Posted May 3, 2014 Author Share Posted May 3, 2014 (edited) Let's unpack this a little by annotating as we go. p is prime, [latex]a\in\mathbb{N}, p\nmid a[/latex] Let [latex]A=\{a,2a,3a,\cdots ,(p-1)a\}[/latex] Now, we want to show that these p-1 numbers in A are all the nonzero residues mod p. In other words, no two of these are equal mod p. So, assume that two of them are equal. Let [latex]ra\equiv sa\pmod{p}[/latex] with [latex] 1 \leq r, s \leq p-1[/latex] Then: ra=mp+R and sa=np+R What is R? This is a little messy. I think I would just skip that line entirely since there's an easier way to go. Note that if [latex]ra\equiv sa\pmod{p}[/latex] then [latex]p |(ra - sa) = (r - s) a[/latex] Then you can apply the theorem that [latex]p \mid ab[/latex] implies that either [latex]p \mid a[/latex] or [latex]p \mid b[/latex], plus the fact that [latex]p \nmid a[/latex] to conclude that [latex]p | (r - s)[/latex] So [latex]r\equiv s\pmod{p}[/latex] But r and s are between 1 and p - 1, so the only way they can be equivalent mod p is if r = s. In other words, the set A contains a complete set of nonzero residues mod p in some order. That's what they mean by: The elements of A must thus all be different and congruent with the elements of the set [latex]B=\{1,2,3,\cdots ,(p-1)\}[/latex]. The sequence is not important. And now tell us the rest R is the remainder. I get everything until you get to "In other words, the set A ..." Why is this? I do see that if both r and s are between 1 and p-1, they can only be equivalent modulo p if they're equal... But what does this prove? Only thing it shows, as I see it, is that all the elements of A are different from each other; but this was kinda logic? I mean, if this is the reason of that step, to show that the elements of A are different... Why? Isn't it just logic that a isn't equal to 2a, to 3a and so on? EDIT: I see what you're doing, and I get it.. So you're showing that ra and sa can only be equivalent mod p, if and only if r and s are equal? But why not just say that a isn't equal to 2a? and so on? RE-EDIT: oh no wait, I think I get it. Thanks! The rest of the proof is rather easy: Since the elements of A and B are, in some order, equivalent modulo p, the product of all elements of A should be equivalent modulo p with the products of all elements of B. Work it out, and you get Fermat's little theorem Edited May 3, 2014 by Function Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now