Results 1 to 4 of 4

Math Help - Simple polynomial problem?

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    12
    Awards
    1

    Simple polynomial problem?

    A problem from G.E. Andrews's "Number Theory":

    Suppose g is a primitive root modulo p (a prime) and m | p-1, where (0<m<p-1). How many integral solutions are there of the congruence
    x^m - g "congruent to" 0 (mod p).

    Proposed solution:

    Assume there is at least one such x.

    p ~|g since g is a primitive root.
    Therefore p ~| x ^ m and p ~| x.

    p ~| x implies x ^ p-1 "congruent to" 1 (Euler's Theorem).

    mk= p-1 for some k. (hyp)

    x ^ mk "congruent to" 1

    x ^ m "congruent to" g. (hyp)

    x ^ mk "congruent to" g ^ k. (raise to a power)

    g ^ k "congruent to" 1. (Congruence is an equivalence rel.)

    k < p-1

    g is not a primitive root, since g does not belong to p-1.

    Conclusion: there is no x such that x^m "congruent to" g.

    Is this conclusion acceptable (or almost acceptable!) ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Very good. I'm not sure I understand your notation very well but the solution is correct. In group-theoretic terms, what you have shown is that if a group G is cyclic of order n, generated by x, and m|n, then x^m is not a generator of G. In fact the condition m|n is stronger than required - it suffices that (m,n)>1, because then x^m has order \frac{n}{(m,n)}<n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Nivla View Post
    A problem from G.E. Andrews's "Number Theory":

    Suppose g is a primitive root modulo p (a prime) and m | p-1, where (0<m<p-1). How many integral solutions are there of the congruence
    x^m - g "congruent to" 0 (mod p).

    Proposed solution:

    Assume there is at least one such x.

    p ~|g since g is a primitive root.
    Therefore p ~| x ^ m and p ~| x.

    p ~| x implies x ^ p-1 "congruent to" 1 (Euler's Theorem).

    mk= p-1 for some k. (hyp)

    x ^ mk "congruent to" 1

    x ^ m "congruent to" g. (hyp)

    x ^ mk "congruent to" g ^ k. (raise to a power)

    g ^ k "congruent to" 1. (Congruence is an equivalence rel.)

    k < p-1

    g is not a primitive root, since g does not belong to p-1.

    Conclusion: there is no x such that x^m "congruent to" g.

    Is this conclusion acceptable (or almost acceptable!) ?

    More than acceptable: it is, as far as I can see, true.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2009
    Posts
    12
    Awards
    1
    Bruno J.: Thanks for the group-theoretic reference! In this case, the order n is p-1, the number of members of the reduced residue set: {g, g^2, g^3, ... , g^p-1} (I believe).

    I have to admit my need to refresh my memory on the order of a cyclic group, but I follow you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple Polynomial fit problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 15th 2010, 06:57 AM
  2. Stumped by "simple" polynomial problem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 4th 2009, 09:05 PM
  3. Simple Polynomial Multiplication problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 21st 2009, 05:09 PM
  4. (Simple?) Polynomial problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 27th 2008, 08:11 PM
  5. Another simple polynomial question
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 4th 2008, 10:10 AM

Search Tags


/mathhelpforum @mathhelpforum