Results 1 to 4 of 4

Math Help - Proving numbers in sequences and summation

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    92

    Proving numbers in sequences and summation

    Let n be a positive integer, and let k be the number of integers < n that are relatively prime to n.

    Show that n is prime if and only if k = n-1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    Quote Originally Posted by racewithferrari View Post
    Let n be a positive integer, and let k be the number of integers < n that are relatively prime to n.

    Show that n is prime if and only if k = n-1.
    It's pretty straight forward isn't it? Since there are exactly n-1 integers less than n to begin with, that is saying "n is prime if and only if it is relatively prime to every number less than it".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    92
    Can you elaborate your answer in an easy way so that I can understand, because I am new to this and I don't want my teacher to think that I have cheated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Note that what this is really saying is that n has exactly two divisors. And since 1,n are always divisors of n we may conclude that they are the only divisors. But that is the defintion of primeness, that only the number itself and one are positive divisors.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Combinatorics Summation Identitiy
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 15th 2011, 08:52 AM
  2. Summation proving 2
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: May 21st 2011, 05:39 AM
  3. summation proving
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 6th 2011, 03:42 AM
  4. Sequences and Series - summation notation
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: May 4th 2010, 02:22 AM
  5. proving this summation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 30th 2009, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum