Results 1 to 6 of 6

Math Help - Modular Arithmetic

  1. #1
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Modular Arithmetic

    Is there a simple way to prove that ɸ(p) = p - 1
    I would appreciate any suggestions
    Follow Math Help Forum on Facebook and Google+

  2. #2
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Re: Modular Arithmetic

    Do you need to refer to 'Euler's Theorem' and 'Fermats Little Theorem' in the proof?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    195
    Thanks
    5

    Re: Modular Arithmetic

    If p is a prime then you want a proof of Fermats Little Theorem. If p is composite then a proof of Euler's totient function will work.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Re: Modular Arithmetic

    Thank you.
    p is prime.
    I was looking at a proof of Fermats little Theorem on line but I still cannot see how ɸ(p) = p - 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    195
    Thanks
    5

    Re: Modular Arithmetic

    Quote Originally Posted by mlg View Post
    Thank you.
    p is prime.
    I was looking at a proof of Fermats little Theorem on line but I still cannot see how ɸ(p) = p - 1.
    Well $\phi(n)$ is defined as the number of natural numbers such that $gcd(a,n)=1$ for $a>n$; another way of saying this is that a and n are relatively prime. If n is, say 9, then from the set $\{1,2,3,4,5,6,7,8\}$ only $\{1,2,4,5,7,8\}$ are a's which are relatively prime to 9, our n in this example, so $\phi(9)=6$.

    In the specific case you bring up n is a prime (from $ɸ(p) = p - 1$). Since every natural number less then p is relatively prime to p all you have to do is count the natural numbers less then p to get your $\phi(p)$, which happens to be $p-1$.

    The definition I have is; $\phi(n)=$the number of integers a that satisfy $0\leq a<n$ and $gcd(a,n)=1$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    mlg
    mlg is offline
    Junior Member
    Joined
    Oct 2013
    From
    Ireland
    Posts
    64

    Re: Modular Arithmetic

    Thank you for your time and effort.
    Although Modular arithmetic is new to me, what you have shown now makes a lot of sense to me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Algebra Forum
    Replies: 6
    Last Post: May 4th 2014, 01:36 PM
  2. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 11th 2011, 12:27 PM
  3. Modular arithmetic.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 10th 2011, 06:21 PM
  4. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 15th 2011, 09:51 PM
  5. Modular arithmetic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 18th 2008, 06:01 PM

Search Tags


/mathhelpforum @mathhelpforum