Results 1 to 6 of 6

Math Help - Help With primitive roots

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    28

    Help With primitive roots

    Hi guys, i dont understand WHAT is going on in this question...

    How do they just "choose" 2, 3 and 5 to check for ?

    Also in the power why is it 1606/2 then 1606/11???

    I really dont understand whats going on

    heres the question and solution

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Well remember by the Fermat-Euler theorem that a^{\phi(n)} \equiv 1 \mod n, where \phi(n) is the number of things less than n that are relatively prime to n.

    Often times, a number doesn't need to be raised all to the way to \phi(n) before it gives back 1 though.
    For example, \phi(8) = 4, and while 3^4 = 81 \equiv 1 \mod 8, it is also true that 3^2 \equiv 1 \mod 8. So 3 is not a primitive root mod 8.

    We call the order of a number the smallest positive number that number is raised to in order to get 1. In the above example, the order of 3 is 2, because 3^2 \equiv 1\mod 8, but no lower power will work.

    So a primitive root mod n is a number whose order is equal to \phi(n). It is a proven fact that the order of a number will always divide \phi(n). This fact will be used.

    In the problem you have, we are looking for primitive roots mod 1607.
    Now 1607 is prime, so \phi(1607) = 1606 because everything less than it is obviously relatively prime to it.

    If a number were NOT primitive, then its order would be less than 1606, but also its order would divide 1606.

    A good strategy for finding primitive roots is just to test numbers.
    1 is obviously not primitive because its order is 1.
    Looking at 2, we raise it to powers that divide 1606; Try raising it to 1303 power (which is 1606/2, as was done in the solution). Sure enough, this gives 1, so the order of 2 is at most 1303, which means 2 cannot be primitive. (by the way, I'm guessing you know how at least to raise numbers to very high powers using mods without working out massive calculations. On a normal day, outside the world of mods, 2^{1303} is a daunting task at best.)
    Next we look at 3, and do the same thing. Again, we get 1 back, so 3 cannot be a primitive root.
    Now next would be 4, but 4 is skipped because it's a power of 2, and we already threw 2 away as a possibility.

    Next is 5, and actually the solution you posted has a typo in it.
    First we check the 1606/2 power, and instead of 1 we get -1. So far so good.
    Next we check 1606/11 power, and again we don't get 1. Good news again.
    Finally, we check the last power, which is 1606/73 (in the pic posted, they have this printed wrong) and again we don't get 1. So 1606 must be the order of 5, and so 5 is a primitive root.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Hey,thanks for the help..

    I still dont understand how you can just "divide" the number by 2 and know that it gives 1?

    I know (Now) its just easy to read the soultion and say "yes this gives 1" but when your trying to solve it from scratch, When i power numbers i use the fast powering algorithm, which is (relativley) time consuming, so how can i be trying all these numbers inorder to get somthing congruent to 1?

    for example there id need to calculate 2^803, which would take a good 5 minutes?

    Is the fast powering algorithm optimal to be using in an exam?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Quote Originally Posted by BruceBronson View Post
    Hey,thanks for the help..

    I still dont understand how you can just "divide" the number by 2 and know that it gives 1?

    When i power numbers i use the fast powering algorithm, which is (relativley) time consuming, so how can i be trying out all these numbers inorder to get somthing congruent to 1?

    for example there id need to calculate 2^803, which would take a good 5 minutes?

    Is the fast powering algorithm optimal to be using in an exam?
    I've never heard it called that, but I'm sure that's the standard method. If it only takes 5 minutes to do that, you're probably using the right method.
    Of course I don't know your professor, but in my experience exam questions are not made unnecessarily complicated in terms of calculation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Fast powering is the method where u have thre 3 columns and the first is half the entry in the previous, 2nd is the square mod m of the previous, and the last is the product of 2 entries mod m

    Is that the fastest possible way to do it?

    Ps. thanks for the help
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    The primitive root of a prime p is such a number a (say between 1 and p-1) so that the order of a is p-1. Now by Fermat's theorem we know that a^{p-1} \equiv 1, but it is not necessaryiliy the smallest possible exponent. So we need to check whether or not it is the smallest.

    However, it does not need we need to show a^k\not = 1 for k=1,2,...,p-2 by checking each possible case. We can use the fact that the order of the element divides p-1 and just check the possible orders of an element. That is what the problem was doing.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 10th 2011, 06:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 09:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 15th 2007, 10:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 08:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2006, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum