We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
238
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+2343 
+1

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

24 Online Users

avatar
avatar