+0  
 
+1
27
1
avatar

 

There is a set S of integers {1,2,⋯,100}. How many elements does the largest subset of S have so that the product of no 2 distinct elements in S is a perfect square? Prove that this is the maximum.


My idea so far is to make the subset contain 1, all the primes, all the semiprimes (numbers that are p*q where p and q are distinct primes), and all the numbers that are p*q*r where p,q,r are distinct primes. Intuitively, this seems like it would make the largest subset, but I'm not sure how to prove it.

 
 Sep 10, 2021
 #1
avatar
0

The largest number of elements in S is 20, one for each congruence class modulo 5.

 
 Sep 11, 2021

30 Online Users

avatar