[Math] Taking a square root of a number: finding an upper limit for factors of a non-prime number (Eratosthenes)
- Get link
- X
- Other Apps
Eratosthenes has discovered that "a non-prime number has its factor (other than 1) that is less than the square root of the number."
1) Task: finding an upper limit for factors of a non-prime number.
2) Motivation: suppose number = 100
square root (100) = 10
factors of 100 = {1, 2, 4,5, 10, 20, 25, 50, 100}
Note that factors of 100 exist before the square root of 100 (= 10). Namely, 1, 2, 4, 5 are those. With exception of 1, we have found prime factors of 10 that are less than 2,4, and 5. That's good enough information to determine that 100 is not a prime number.
3) An idea for mathematical proof would be:
1. suppose a number is a non-prime number. That is, this number = M * N where M>N > 0
2. multiplying N to both sides of the inequality M>N results M*N > N^2
3. by design, this number = M*N > N^2
4. taking the square root, we have (M*N)^(1/2) > N
conclusion: a factor of a non-prime number is less than this number itself.
4) Tests
Test 1: let number = 100 = 5*20 = 2*50 = 4*25 = 1*100 = 10*10
square(100) = 10 -> there exists a factor(other than 1) of 100 that is less than 10: namely, 2,4,5.
Test 2: let number = 56 = 1*56 = 2*28 = 4*14 = 7*8
square(56) = 7.48331477355.... -> there exists a factor(other than 1) of 56 that is less than 7.48: 2,4,7
End
- Get link
- X
- Other Apps
Comments
Post a Comment