1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory Help

  1. Feb 16, 2012 #1
    1. The problem statement, all variables and given/known data

    Let [itex]p[/itex] be an odd prime. Show that there exists [itex]a\in\mathbb{Z}[/itex] such that [itex][a]\in\mathbb{Z}^{\times}_{p}[/itex] is a generator and [tex]a^{p-1}=1+cp[/tex] for some [itex]c[/itex] coprime to [itex]p[/itex].

    2. Relevant equations



    3. The attempt at a solution
    I honestly have no idea where to even start with this. Any help will be much appreciated, no full solutions though!
     
  2. jcsd
  3. Feb 16, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You could start with Fermat's Little Theorem.
     
  4. Feb 16, 2012 #3
    Well I know its obvious that [itex]a^{p-1}\equiv 1 (\mod p)[/itex] since [itex][a]\in\mathbb{Z}_{p}^{\times}[/itex]. Hence there exists [itex]k\in\mathbb{Z}[/itex] such that [itex]a^{p-1}=1+kp[/itex]. How do I show that [itex]\gcd (k,p)=1[/itex]?
     
  5. Feb 16, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Offhand, I don't know. You were asking for a hint to start and no full solutions. I'll think about it though, if you don't find the solution first.
     
  6. Feb 16, 2012 #5

    Deveno

    User Avatar
    Science Advisor

    for [a] to be a generator, we also need to know that p-1 is the smallest positive integer k for which:

    ak ≡ 1 (mod p)

    i suggest asking yourself a similar, but related question:

    suppose d|(p-1). how many elements of Zpx are of order d?

    hint: suppose a is of order d.

    (i suppose i "should write" [a] instead of a. i mean the modulo class, NOT the integer)

    look at the set {1,a,a2,...,ad-1}.

    this is a cyclic group, how many generators does it have?

    hint #2: eventually, you'll have to drag in the totient function into this. why did i suggest looking at those d that divide p-1?
     
    Last edited: Feb 16, 2012
  7. Feb 16, 2012 #6
    Any element [itex]a^{r}[/itex] such that [itex]\gcd(r,d)=1[/itex] is a generator.
     
  8. Feb 16, 2012 #7

    Deveno

    User Avatar
    Science Advisor

    yes, that is true. and how many of those "r's" are there?
     
  9. Feb 16, 2012 #8
    The size of [itex]\mathbb{Z}_{p}^{\times}[/itex] is [itex]\phi (p)=p-1[/itex]
     
  10. Feb 16, 2012 #9
    [itex]\phi (d)[/itex] many.
     
  11. Feb 16, 2012 #10

    Deveno

    User Avatar
    Science Advisor

    yes, that is also true, and you'll want to use that fact later on. how does "d" enter into this?

    exactly! now...given any a of order d, how many "other elements" of order d, do we get "for free" along with it?

    and...do you know of any way to relate φ(d) and φ(p-1)?
     
  12. Feb 16, 2012 #11
    If we take [itex]d=p-1[/itex], then there are only [itex]\phi (p-1)[/itex] many generators of [itex]\mathbb{Z}_{p}^{\times}[/itex]. Is this right?

    Since [itex]d|p-1[/itex], it follows that [itex]\phi(d)|\phi(p-1)[/itex]. Hence there exists [itex]k\in\mathbb{Z}[/itex] such that [itex]\phi(p-1)=k\phi(d)[/itex].
     
  13. Feb 16, 2012 #12

    Deveno

    User Avatar
    Science Advisor

    we only know that if we already know that there is in fact an element a of order p-1, which is what we're trying to prove!

    we don't even know if there are any elements of order d, but if there are, how many must we have (at least)?

    ok, let's step back for a minute, and see if you can glimpse where we're going:

    every element of Zpx has SOME order, and we know that the order of any element has to divide p-1, by a theorem of Lagrange.

    let's call the number of elements of order d, f(d).

    so if the divisor list of p-1 is 1 = d1,d2,...,dk = p-1

    p -1 = f(d1) + f(d2) +...+ f(dk)

    [tex]= \sum_{d|p-1} f(d)[/tex]

    for every d that divides p-1, f(d) is either ___ or _____ ?
     
    Last edited: Feb 16, 2012
  14. Feb 16, 2012 #13
    For every [itex]d|p-1[/itex], it follows that every [itex]f(d)[/itex] is either [itex]\phi(d)[/itex] or [itex]0[/itex], because we haven't verified the fact that there exists an element of order [itex]d[/itex] for each [itex]d|p-1[/itex].
     
  15. Feb 16, 2012 #14

    Deveno

    User Avatar
    Science Advisor

    great! glad to see you're still with me on this.

    now, do you know the answer to this question?

    [tex]\sum_{d|p-1} \varphi(d) = ?[/tex]
     
  16. Feb 16, 2012 #15
    Yep :)
    [tex]\sum_{d|p-1}\phi(d)=p-1[/tex]
     
  17. Feb 16, 2012 #16

    Deveno

    User Avatar
    Science Advisor

    and is it not true that for every d that divides p-1:

    f(d) ≤ φ(d)?
     
  18. Feb 16, 2012 #17
    Yep since [itex]f(d)[/itex] is either [itex]\phi(d)[/itex] or [itex]0[/itex]; both of which are less than or equal to [itex]\phi(d)[/itex]. And since [itex]\sum_{d|p-1}f(d)=\sum_{d|p-1}\phi(d)[/itex], it follows from the previous sentence that [itex]f(d)=\phi(d)[/itex]. So now we know that [itex]\phi(d)[/itex] is exactly the number of elements in [itex]\mathbb{Z}_{p}^{\times}[/itex] that have order [itex]d[/itex]. Hence, for each [itex]d|p-1[/itex], there exists exactly [itex]\phi(d)[/itex] many (which is non-zero) elements in [itex]\mathbb{Z}_{p}^{\times}[/itex] whose order is [itex]d[/itex].
     
  19. Feb 16, 2012 #18

    Deveno

    User Avatar
    Science Advisor

    so now we've established existence for EVERY d that divides p-1. and one of those divisors is....?
     
  20. Feb 16, 2012 #19
    We can take [itex]d=p-1[/itex] and hence there exists [itex]\phi(p-1)[/itex] many elements of [itex]\mathbb{Z}_{p}^{\times}[/itex] whose order is [itex]p-1[/itex]. But since the order of [itex]\mathbb{Z}_{p}^{\times}[/itex] is [itex]p-1[/itex], it follows that these elements are exactly the generators of [itex]\mathbb{Z}_{p}^{\times}[/itex]. Hence, we've show that there exists at least a single generator of [itex]\mathbb{Z}_{p}^{\times}[/itex].

    So let [itex]a\in\mathbb{Z}_{p}^{\times}[/itex] be one of these generators. By Fermat's Little Theorem we have [itex]a^{p-1}\equiv 1[/itex] [itex]\mod {p}[/itex]. Hence there exists [itex]k\in\mathbb{Z}[/itex] such that [itex]a^{p-1}=1+kp[/itex].
     
  21. Feb 16, 2012 #20

    Deveno

    User Avatar
    Science Advisor

    indeed, we've shown that there's usually a lot of generators.

    there's just one more matter to clear up.

    we know that there is some a with order p-1, so of course ap-1 = 1 + kp.

    but...we haven't yet shown gcd(k,p) = 1. any thoughts?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number Theory Help
  1. Number theory help (Replies: 1)

  2. Number theory help (Replies: 4)

  3. Number theory help (Replies: 3)

  4. Number theory help (Replies: 26)

Loading...