Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prime number problem, pure maths, explain this solution

  1. May 8, 2007 #1
    1. The problem statement, all variables and given/known data

    Prove that for every k >= 2 there exists a number with precisely k divisors.


    I know the solution, but don't fully understand it, here it is;


    Consider any prime p. Let n = p^(k-1). An integer divides n if and only if it has the form p^i where 0<= i <= (k-1). There are k choices for i, therefore n has exactly k divisors.

    Could someone fully explain the thought process involved in finding the solution, I understand p^i etc, just don't know where p^(k-1) comes from.
     
  2. jcsd
  3. May 8, 2007 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If you understood the though process, you'd know where [tex]p^{k-1}[/tex] came from. Given the problem, one can decide to be clever and take a prime, say p. Then if we look at

    1,p,p2,...pk-1

    Then 1, p, p2, .... ,pk-1 all divide pk-1, and no other numbers do. Hence, we found a number with exactly k divisors
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook