+0

# help

0
374
1

An integer \(n\) is said to be square-free if the only perfect square that divides \(n\) is \(1^2\). How many positive odd integers greater than 1 and less than 100 are square-free?

Jan 3, 2019

#1
+2419
+2

This is how I would personally approach this problem.

#1: List all the integers from 1 to 100.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

#2: Eliminate all even numbers and 1 and 100 from the list since we are only interested in "square-free" numbers bounded between 1 and 100.

 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99

#3: Eliminate multiples of the first perfect square I will test, 3^2, or 9. I am not testing 2^2, or 4 because I have already eliminate the even numbers from the list, so no multiples of 4 remain in the list right now.

 3 5 7 11 13 15 17 19 21 23 25 29 31 33 35 37 39 41 43 47 49 51 53 55 57 59 61 65 67 69 71 73 75 77 79 83 85 87 89 91 93 95 97

#4: Eliminate the multiples of the second perfect square I will test, 5^2, or 25. Again, I am not testing 4^2, or 16, because even numbers have already been filtered out.

 3 5 7 11 13 15 17 19 21 23 29 31 33 35 37 39 41 43 47 49 51 53 55 57 59 61 65 67 69 71 73 77 79 83 85 87 89 91 93 95 97

#5: Eliminate the multiples of 7^2, or 49. Only one number gets eliminated.

 3 5 7 11 13 15 17 19 21 23 29 31 33 35 37 39 41 43 47 51 53 55 57 59 61 65 67 69 71 73 77 79 83 85 87 89 91 93 95 97

#6: Normally, I would eliminate the multiples of 9^2, but I already sifted out the multiples of nine, so all the multiples of 9^2 have already been eliminated from the list.

#7: There is no need to eliminate the multiples of 11^2, or 121, since that multiple is larger than the largest number we are testing, so we can stop the process here. The numbers that remain are "square-free."

In a list, they are 3,5,7,11,13,15,17,19,21,23,29,31,33,35,37,39,41,43,47,51,53,55,57,59,61,65,67,69,71,73,77,79,83,85,87,89,91,93,95,97.

Jan 4, 2019