+0  
 
0
962
1
avatar

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
avatar+2439 
+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

2 Online Users