Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By mak29
  • 1 Post By Plato

Thread: Finding factors of a number

  1. #1
    Senior Member
    Joined
    Mar 2017
    From
    Massachusetts
    Posts
    331
    Thanks
    2

    Question Finding factors of a number

    Hi,

    I hope someone can help.

    I am trying to developed an algorithm which based on a given input, call it x, determines whether x is prime.

    One way to do this is to check all the numbers (starting at 2) up to x/2 is divisible by x. If there is such a number, then x is not prime. I understand this strategy completely.

    However, another way to to check all numbers (starting at 2) up to the square root of x. Can someone please explain to be why this works?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2018
    From
    India
    Posts
    16
    Thanks
    5

    Re: Finding factors of a number

    For instance, we have the pairs (1,12), (2,6), and so on as factors of 12 as shown in the first table.



    Notice that the 4th, 5th, and 6th pairs are just “reverses” of the first three pairs. In effect, we just need to include the first three pairs to be sure that we have all the factors. This is also the similar in the second example. We only need to test the divisibility up to 4 and we have already all the factors. No need to test divisibility by 5 up to 16. (To verify further, try factors of other composite numbers.)



    You have probably noticed that there is some sort of “middle number” in both tables denoted by the red-colored text. After the middle number, the pairs are mere repetitions of the other pairs.

    In the first table, the middle number is 3, while in the second table, the middle number is 4. Four is the square root of 16, and testing more perfect squares (the reader is encouraged to do so) will confirm the observation.

    From above, we can conjecture that every composite number has a factor less than or equal to its square root. Proving this is the same as proving that a number that has no divisor greater than 1 and less than its square root is prime.

    The Formal Proof

    Conjecture: Every composite number has a proper factor less than or equal to its square root.

    Proof: We use proof by contradiction. Suppose n is composite. Then, we can write n = ab, where a and b are both between 1 and n. If both $a > \sqrt{n}$ and $b> \sqrt{n}$, then$ (a)(b) > (\sqrt{n})(\sqrt{n})$ which means that $ab > n$. This contradicts our assumption that $ab = n$. Hence, at least one of $a, b$ is less than or equal to $\sqrt{n}$. That is, if $n$ is composite, , then n has a prime factor $p \le \sqrt{n}$.
    Last edited by Plato; Jan 3rd 2019 at 01:10 PM. Reason: Fixed LaTeX
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,332
    Thanks
    3223
    Awards
    1

    Re: Finding factors of a number

    Quote Originally Posted by otownsend View Post
    I am trying to developed an algorithm which based on a given input, call it x, determines whether x is prime.
    One way to do this is to check all the numbers (starting at 2) up to x/2 is divisible by x. If there is such a number, then x is not prime. I understand this strategy completely.
    However, another way to to check all numbers (starting at 2) up to the square root of x. Can someone please explain to be why this works?
    This reply in no way is intended to discourage your project.

    If $n=4276800$ then $n$ can be factored as $2^6\cdot 3^5\cdot 5^2\cdot 11$, SEE HERE. On that webpage we are told that $n$ has $252$ divisors.

    Here is more interesting question. Suppose $\{p,q,r,s,t\}$ is a set of five prime numbers, and $N=p^4\cdot q^3\cdot r^7\cdot s^2\cdot t^6$.

    How many factors does the number $N$ have?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Mar 2017
    From
    Massachusetts
    Posts
    331
    Thanks
    2

    Re: Finding factors of a number

    Hey, thanks for your reply mak21. The formal proof you provided is clear to be. However, you seem to be referring to a table that isn't actually available in the post itself ... are you missing an attachment or link? Please let me know.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Smallest number with given number of factors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 26th 2012, 12:05 PM
  2. factors of number
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Apr 22nd 2012, 08:31 AM
  3. factors of a number
    Posted in the Algebra Forum
    Replies: 0
    Last Post: Apr 8th 2010, 07:46 AM
  4. Number of factors
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 6th 2008, 06:02 AM
  5. help please, number of factors
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Dec 28th 2007, 09:04 AM

Search Tags


/mathhelpforum @mathhelpforum