Results 1 to 2 of 2

Math Help - Order of Integer Questions

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    Order of Integer Questions

    1) Show that if n is a positive integer and a and b are integers relatively prime to n such that (ord_{n}a, ord_{n}b) = 1, then ord_{n}(ab) = ord_{n}a * ord_{n}b

    2) Let p be a prime divisor of the Fermat number F_{n} = 2^{2n} + 1
    a) Show that ord_{p}2 = 2^n + 1
    b) From part (a), conclude that 2^{n+1} \mid (p-1), so that p must be of the form 2^{n+1}k + 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    For the first one...

    (By the way Fermat's number is from the form: 2^{2^n}+1 when n=0,1,...

    For your question now...

    I don't use to work with ord notation, so...

    ord_n(a)=t, ord_n(b)=s and ord_{n}(ab)<br />
=w

    From ord_{n}(ab) which can be written as:

    (ab)^w\equiv1(mod {n}), we can deduce:

    (ab)^{wt}\equiv 1(mod {n}), and from (a)^{wt}\equiv 1(mod {n}), we get:

    (b)^{wt}\equiv 1(mod {n})

    From your first theorem on this subject of orders... we can say that: {s}\mid {wt}, but gcd(w,t)=1, hence: {t}\mid {w}...

    Similarly we can prove: {s}\mid{w}.

    Now, we have: {t}\mid {w} and {s}\mid {w}, hence: {ts}\mid {w}.


    And the last part:

    We have given that:

    a^t\equiv1(mod{n}) and b^s\equiv1(mod{n}),
    so: (ab)^{ts}=(a^t)^s(b^s)^t\equiv1(mod{n}) and from the theorem I mentioned before we get: {w}\mid {ts}, and with the {ts}\mid {w} (from the last part), we may deduce that w=ts
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: March 6th 2011, 10:08 AM
  2. Order of Integer Question
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 27th 2010, 08:51 PM
  3. Order of Integer Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 16th 2007, 05:45 PM
  4. Number theory, order of an integer
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 05:53 AM
  5. order of an integer
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 21st 2006, 05:37 AM

Search Tags


/mathhelpforum @mathhelpforum