Results 1 to 5 of 5

Math Help - abstract algebra [primitive root mod n, euler theorem, fermat theorem]

  1. #1
    Banned
    Joined
    Jan 2011
    Posts
    2

    abstract algebra [primitive root mod n, euler theorem, fermat theorem]

    Try this qn


    For a prime number p the set of co-primes less than or equal to it is given by {1,2,3,4,...p-1} .

    We define f(x,p) 0<x<p = 1 if and only if all the numbers from 1 to p-1 can be written as a power of x in modulo-p arithmetic .

    Let n be the largest 12-digit prime number . Find the product of all integers j less than n such that f(j,n)=1, in modulo-n arithmetic
    n is 999999999989
    The answer for this is 1.
    How is it??
    Please can anyone explain?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466
    Well, it is pretty easy to guess from the answer what happens. You are asked for "the product of all positive integers less than n such that ..." and find that the product is 1. The only way a product of integers can equal 1 is if all the integers are 1! It must be the case that the only positive integer, x, such that "every integer from 1 to p-1 can be written as a power of x in modulo p" is 1 itself.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Jan 2011
    Posts
    2
    then the function f(j,n) must be j mod n
    This only 1 mod 999999999989 = 1

    But how to find out that f(j,n) = j mod n ??
    Last edited by stevanity; January 9th 2011 at 07:28 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by HallsofIvy View Post
    Well, it is pretty easy to guess from the answer what happens. You are asked for "the product of all positive integers less than n such that ..." and find that the product is 1. The only way a product of integers can equal 1 is if all the integers are 1! It must be the case that the only positive integer, x, such that "every integer from 1 to p-1 can be written as a power of x in modulo p" is 1 itself.
    This is not true.

    f(n, p) is a function which returns 1 if and only if n is a generator of the multiplicative group of the field, U_p.

    This result actually holds in general. That is, \displaystyle\prod_{f(n, p) = 1, 0<n<p}n = 1 for all p. The reason is actually quite elegant...if you know about groups. I am therefore going to assume that you, stevanity, know about groups. If you do not, no probs! I'll write it down a different way.

    So, denote \{1, 2, \ldots, p-1\} by U_p. Writing S = \{a: <a> = U_p\} then you have two things to prove:

    1. If a \in S then a^{-1} \in S,
    2. If a \in S then a^{-1} \neq a for p>2.

    Can you see why proving these two things solves the problem?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Chicago, IL
    Posts
    2,844
    Thanks
    3
    Closing all threads by this user, since its suspected that he's cheated on an official programming competition.

    Thread closed.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Root/Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 3rd 2010, 09:31 PM
  2. Working with mod p (Euler's and Fermat's Theorem)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 22nd 2010, 11:22 PM
  3. Primitive Root Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 28th 2008, 09:27 AM
  4. Abstract Algebra: Lagrange's Theorem 2
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 16th 2008, 10:46 AM
  5. Abstract Algebra: Lagrange's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 16th 2008, 09:02 AM

Search Tags


/mathhelpforum @mathhelpforum