Number Theory Help

• Forbiddensinner

  18 Apr 10, 19:22

  Is it possible for a positive integer n which has at least two distinct prime factors to have exactly 13 positive divisors? Justify your answer.

  I have considered doing case-by-case, but besides that, are there any better ways? I am very sure there is no such integer though.

   

   

   

• Forbiddensinner

  18 Apr 10, 21:10

  Originally posted by Forbiddensinner:

  Is it possible for a positive integer n which has at least two distinct prime factors to have exactly 13 positive divisors? Justify your answer.

  I have considered doing case-by-case, but besides that, are there any better ways? I am very sure there is no such integer though.

   

   

   

  Tks to those who have a look.

  I just figured out how to prove it already. 

  Mods please help to lock thread, tks. 

• wee_ws

  18 Apr 10, 21:11

  Hi,

    Thanks for sharing an interesting question.

    Let's say n = (p_1)^(a_1) x (p_2)^(a_2), since it has at least 2 distinct prime factors.

    Number of divisors of n = (a_1 + 1) x (a_2 + 1).

    Can (a_1 + 1) x (a_2 + 1) = 13?

    Thanks!

  Cheers,
  Wen Shih

• Forbiddensinner

  18 Apr 10, 21:39

  Originally posted by wee_ws:

  Hi,

    Thanks for sharing an interesting question.

    Let's say n = (p_1)^(a_1) x (p_2)^(a_2), since it has at least 2 distinct prime factors.

    Number of divisors of n = (a_1 + 1) x (a_2 + 1).

    Can (a_1 + 1) x (a_2 + 1) = 13?

    Thanks!

  Cheers,
  Wen Shih

  Thank you Sir.

  What I am thinking of is very similar, and draws from what I have learnt in Finite Mathematics (Though with some twisting here and there)

  Suppose that an integer n is made up of j distinct primes, a_1, a_2,....a_j, where j is an integer greater than 1.

  Let n=a_1^m_1 X a_2^m_2 X .... a_j^m_j, where m_i's are all positive integers.

  Then the number of positive divisors of n will be (m_1 + 1) X (m_2 + 1) X ... X (m_j + 1)

  Notice that m_1+1, m_2+1, ..., m_j+1 are each at least 2, whereas 13 can only be factorised into 1 X 13, and thus by Fundamental theorem of Arithmetic,  this is a contradiction.

  Hence, if an integer has at least two prime factors, it is not possible to have 13 positive divisors, or any other prime amount of positive divisors (E.g. 2, 3, 5, 7...)

• wee_ws

  18 Apr 10, 22:15

  Hi Forbiddensinner,

    Good effort!

  Cheers,
  Wen Shih