Let $A$ be an infinite subset of $\mathbb{N}$, and $n$ a fixed integer. For any prime $p$ not dividing $n$, There are infinitely many elements of $A$ not divisible by $p$. Show that for any integer $m >1, (m,n) =1$, There exist finitely many elements of $A$, such that their sum is congruent to 1 modulo $m$ and congruent to 0 modulo $n$.
Problem
Source:
Tags: number theory unsolved, number theory
29.11.2010 01:36
edit: Oh wait sorry I read it as "every prime p dividing n". Still solved and created a different problem haha
29.11.2010 03:00
So let $m=\prod_{i=1}^k p_i ^{e_i}$. There exist infinitely many elements in $A$ not divisible by $p_1$. If you take their residues modulo $mn$ then by PHP some residue class, say $a$, has infinitely many of these elements. So each such $a_i$ has the property: $a_i \equiv a \mod mn$ Which we can decompose to: $a_i \equiv r_1 \mod p_1^{e_1}$ . . . $a_i \equiv r_k \mod p_k^{e_k}$ $a_i \equiv r \mod n$ If we take $x$ of these elements then their sum is $xa$ modulo mn. We want to choose $x$ of them such that the following is satisfied: $xr_1=1 \mod p_1^{e_1}$ $xr_j=0 \mod p_j^{e_j}$ for $j>1$ $xr = 0 \mod n$ This will clearly be satisfied if the following is satisfied: $x=r_1^{-1} \mod p_1^{e_1}$ (note this makes sense since $r_1$ is not a multiple of $p_1$ as constructed above) $x=0 \mod p_j^{e_j}$ for $j>1$ $x=0 \mod n$ But such $x$ does exist by the chineese remainder theorem. Hence we choose $x$ of the $a_i$ so that the sum of them, say $S_1$ satisfies the congruences above. We now remove these elements from $A$ and notice that $A$ still satisfies the property of the problem (as we removed only finitely many elements). Now we do the same process except this time $p_1$ and $p_2$ swap roles. That means we find a bunch of elements whose sum $S_2$ satisfies: $S_2 = 1 \mod p_2^{e_2}$ $S_2 = 0 \mod p_j^{e_j}$ for all $j \neq 2$ $S_2 = 0 \mod n$ Now we keep repeating this process with $p_3$ playing the role $p_1$ played initially etc. until we get sums $S_1,S_2...S_k$ and corresponding elements that have these sums. Because these elements are disjoint, we can take their union and hence the sum will then be: $S=S_1+S_2....+S_k$ Now notice that this sum satisfies: $S=1 mod p_j^{e_j}$ for all $j=1,2...k$ $S=0 \mod n$ The Chineese remainder theorem now readily shows that S satisfies the required properties.