I want to know whether the following property holds:

There exists a constant C such that for any big positive integer N and any nonempty subset M of {1,...,N} there exists a positive integer p(M)$\lt$ logN such that some residue class modulo p(M) contains odd number of elements from M.

A weaker form of the same property is also useful:

There exists a constant C such that for any big positive integer N and any disjoint (but not simultaneously empty!) subsets M, M' of {1,...,N} there exists a positive integer p(M)$\lt$C logN such that some residue class modulo p(M) contains different numbers of elements from M and M'.