1. Limited time only! Sign up for a free 30min personal 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!

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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted