Results 1 to 2 of 2

Math Help - Proving integers?

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    here and there
    Posts
    4

    Proving integers?

    Let n>1 be an integer. Prove that φ (n) | n if and only if n is of the form 2^a 3^b where a≥1 and b≥0 are integers.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2009
    Posts
    19

    Re: Proving integers?

    \varphi(2^a3^b)=2^a3^{b-1} | 2^a3^b

    \frac{n}{\varphi(n)} = \prod_{i=1}^{i=r}\frac{p_i}{p_i-1}
    the rhs denominator is dividable by 2^r if n is not dividable by 2 or 2^{r-1} if it is dividable by 2
    the rhs numerator is dividable only by 2 if n is dividable by a power of 2

    hence for the lhs to become an integer and thus \varphi(n)|n the number of primes in the factorization of n can be at most 2
    hence
    \frac{pq}{(p-1)(q-1)} must be integer

    therefore \frac{pq}{(p-1)(q-1)} \ge 2 equivalent to

    (*) 2 \ge (p-2)(q-2)

    wlog q<p

    examine the two cases:

    1) q=2: \frac{pq}{(p-1)(q-1)} = \frac{2p}{p-1} is integer only for p=3

    2) q \ge 3: then (*) becomes 2 \ge (p-2)(q-2) > p-2 thus p \le 4 since p prime p = 2 or 3 wich is a contradiction to q<p
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving on positive integers?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 21st 2012, 08:31 AM
  2. Replies: 1
    Last Post: May 16th 2011, 07:54 PM
  3. Replies: 2
    Last Post: November 17th 2010, 08:26 PM
  4. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  5. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 02:02 PM

Search Tags


/mathhelpforum @mathhelpforum