Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Some number theory proofs

  1. Mar 16, 2016 #1
    I just want to make sure I understand these number theory proofs.
    [itex] b^{\phi (n)}=1mod(n) [/itex]
    [itex] \phi (n) [/itex] is the order of the group, so b to some power will equal the identity. so thats why it is equal to one. [itex] b^p=bmod(p) [/itex]
    [itex] b^p=b^{p-1}b [/itex]
    [itex] b^{p-1} [/itex] produces the identity since p-1 is the order of the group. so thats why it equals b.
  2. jcsd
  3. Mar 16, 2016 #2


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    Can you clarify what statement you are trying to prove and which statements are the proof? Is b any arbitrary element of the group? Are you trying to show that p = Φ(n)? What is n?
  4. Mar 16, 2016 #3
    And what group are you talking about?

    I think you're trying to prove Euler and Fermat's little theorem somehow, but then you'll need to put in some more details...
  5. Mar 16, 2016 #4
    Its the multiplicative group mod n , n is a natural number. now b is an element of the group. so b to power of the order of the group will contain the order of b.
    that is [itex] b^m=e [/itex] since m is contained in the order of the group,we get the identity. This proves [itex] b^{\phi (n)}=1mod (n) [/itex].
    the second one [itex] b^p=b mod (p) = b^{p-1}b=b^{\phi (p)}b= b mod (p) [/itex]
    I will prove that the order of an element exists. sine b is an element of the group then we can take powers of b like [itex] b^2 , b^3, .... b^n ... [/itex] now for some m and n and m not equal to n,since our group is finite.
    we get [itex] b^m=b^n [/itex] now we multiply both sides by [itex] b^{-n} [/itex]
    so now [itex] b^{m-n}=e [/itex].
    m-n is the order of b.
    Last edited: Mar 16, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted