Generalisation of a problem I have a question which is 
From a set of natural numbers ${1,2,3,...,100}$ , we have to choose a set of cardinality $k$ such that any two elements of that set do neither give thier sum nor their product divisible by $100$ .Find maximum value of $k$.
I encountered this problem as follows
Let we choose all $100$ numbers. Then we have some eliminations to satisfy the requirements.
First , we eliminate the numbers $51,52,53,...,100$ because they can give sum with other numbers which is divisible by $100$
Then we have to eliminate one of the numbers each from $(2,50),(4,25),(10,30),(10,40),(20,5)$ because their product is divisible by $100$
Total number of eliminations are $55$. Therefore maximum value of $k$ is $45$. And of course, this is correct.
Now it seems that this problem could be generalized
Suppose we have ${1,2,3,...,n}$ number. Then $n/2$ will get eliminated. Now from left numbers, we have to deal with the pairs which can give their product divisible by $n$.
This could be related to prime factorisation of $n$. Even though I couldn't find any generalisation.
Now I have two questions
$1.$ Is there any other elegant way to do this problem?
$2.$ Can we generalise this problem? If yes , then what should I do next ?
Please help !!!
 A: For each $d\mid n$ let $A_d=\{\,x\mid 1\le x\le n, \gcd(n,x)=d\,\}$.
Then the product condition reads: 

If $n\mid dd'$ and we pick at least one element of $A_d$, then we must not pick any element of $A_{d'}$. (In the special case $d=d'$ we may pick at most one element from $A_d$)

In particular, we better avoid $A_n$.
As $x\in A_d$ implies $n-x\in A_d$ (except when $x=d=n$), the additive condition implies

We can pick at most half of the elements of $A_d$ (with the exception that we can pick $\frac{|A_d|+1}2$ elements if $|A_d|$ is odd.

Now the problem is less which numbers we pick, but rather from which classes (here concretely: $A_1,A_2,A_4,A_5,A_{10},A_{20},A_{25},A_{50}$ with $ 40, 20, 20, 8, 4, 4, 2,1$ elements, respectively) we pick (any) half. A greedy approach along the product condition seems to work:


*

*Pick $20$ of the elements of $A_1$; this spoils nothing (except that we must not pick from $A_{100}=\{100\}$)

*Pick $10$ of the elements of $A_2$; this spoils picking one element from $A_{50}$

*Pick $10$ elements of $A_4$; this spoils picking one element from $A_{25}$

*Pick $4$ elements of $A_5$; this spoils picking two element from $A_{20}$

*We can pick only one element from $A_{10}$


In total, that's 45 elements.
For general $n>2$, the number achieved by this strategy is
$$\frac12\sum_{d\mid n\atop d^2<n}\phi(n/d)+\begin{cases}1&\text{if }n\text{ is a perfect square}\\0&\text{otherwise}\end{cases}$$
(note that $\phi(n/d)$ will always be even because $n/d>2$), and it seems that this will always be the maximum.
