Results 1 to 3 of 3

Math Help - Prime Power Factorization and Modulo

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    18

    Prime Power Factorization and Modulo

    Show that if the prime power factorization of n-1 is p1^a1...pt^at and that there exists integers xj , for j = 1,2,3,...,t such that for each j:

    xj^[(n-1)/pj] is not congruent to 1 (mod n)

    and

    xj^(n-1) is congruent to 1 (mod n)

    then n is a prime.

    Any ideas on how to prove the above? Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by KatyCar View Post
    Show that if the prime power factorization of n-1 is p1^a1...pt^at and that there exists integers xj , for j = 1,2,3,...,t such that for each j:

    xj^[(n-1)/pj] is not congruent to 1 (mod n)

    and

    xj^(n-1) is congruent to 1 (mod n)

    then n is a prime.

    Any ideas on how to prove the above? Thanks
    The proof can be found here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    28

    Prime Power Factorization and Modulo

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime Factorization Help
    Posted in the Algebra Forum
    Replies: 11
    Last Post: March 23rd 2014, 11:02 AM
  2. Prime Factorization
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 21st 2010, 02:56 PM
  3. Prime-power factorization
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 17th 2008, 04:04 PM
  4. prime factorization 2
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 16th 2008, 12:37 PM
  5. prime factorization
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 18th 2008, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum