Let $S$ be the set of red numbers. For each positive integer $m$, let $S_m$ be the image of the residue map $S\to\{0,1,\dots,m-1\}$, $x\mapsto [x]_m$. Claim 1: Let $m$ be a positive integer whose largest prime divisor is $p$. Then $\varphi(m)\geq\frac{m}{p}$. Proof: Let $p_1<\dots<p_t=p$ be the prime divisors of $m$. Then $\varphi(m)=m\prod_{i=1}^t\left(1-\frac{1}{p_i}\right)\geq m\prod_{i=1}^t\left(1-\frac{1}{i+1}\right)=\frac{m}{t+1}\geq\frac{m}{p}.$ Claim 2: If $a,b$ are coprime positive integers, then $|S_{ab}|\leq |S_a|\cdot |S_b|$. Proof: It is well-known that the function $$f\colon\mathbb Z/ab\mathbb Z\to \mathbb Z/a\mathbb Z\times \mathbb Z/b\mathbb Z$$defined by $x\mapsto (x\mod a, x\mod b)$ is an isomorphism of rings when $a,b$ are coprime. Then the restriction of $f$ to $S_{ab}$ is an injective function from $S_{ab}$ to $S_a\times S_b$. Assume by contradiction that $|S|>\varphi(n)$. Hence there exists a prime which divides both $n$ and some element of $S$. Let $p$ be the maximal prime with this property. Claim 3: There exists $a\in S$ such that $p\mid a$. Proof: By construction. Claim 4: There exist distinct $b,c\in S$ such that $\frac{n}{p}\mid b-c$. Proof: Call a prime $q$ small if $q\leq p$ and large otherwise. There exist unique positive integers $x,y$ such that $n=pxy$, $x$ is divisible by only small primes and $y$ is divisible by only large primes. Since $p$ is the largest prime divisor of $px$, claim 1 proves that $|S_x|\leq x\leq\varphi(px).$ By the choice of $p$, every element of $S$ is coprime to $y$. Thus, $|S_y|\leq\varphi(y)$. Obviously $px,y$ are coprime, so by claim 2, $|S_{\frac{n}{p}}|=|S_{xy}|\leq |S_x|\cdot|S_y|\leq\varphi(px)\varphi(y)=\varphi(pxy)=\varphi(n).$ Thus, by pigeonhole principle, there exist two distinct elements of $S$ whose residue $\pmod{\frac{n}{p}}$ is the same. The claim follows. Finally, assume $a$ satisfies claim 3 and $(b,c)$ satisfies claim 4. Then $b\neq c$ but $n=p\cdot\frac{n}{p}\mid a(b-c)$, contradiction.

Solved with moral support from naman12 . Also thanks to him for latexing the solution. We shall proceed by contradiction. Assume that there are more than $\phi(n)$ such numbers. Then, there exists some prime $q\mid n$ also dividing a red number. Choose $q$ to be maximal. We aim to construct red numbers $b$ and $c$ such that \[ab\equiv ac\pmod n\iff b\equiv c\pmod{\frac nq}\]which is equivalent to showing that there are at most $\phi(n)$ residues of red numbers modulo $\frac nq$. Suppose the number of residues of red numbers modulo $\frac nq$ is $R$ and define the two sets \[S=\{p\mid p~\text{divides}~n~\text{and}p~\text{is prime}\}\]\[S'=\{p\mid p~\text{divides}~n,~p>q,~\text{and}~p~\text{is prime}\}\]Note that $p'\in S'$ implies $p'$ doesn't divide a red number. Thus, we see that \[R=\frac nq\prod_{p\in S'}\left(1-\frac 1p\right)\]We aim to show that \[n\prod_{p\in S}\left(1-\frac 1p\right)\geq\frac nq\prod_{p'\in S'}\left(1-\frac 1{p'}\right)\]This is equivalent to \[q\left(1-\frac 1q\right)\prod_{\substack{p\in S\\p<q}}\geq 1\]or \[q-1\geq\prod_{\substack{p\in S\\p<q}}\frac{p}{p-1}\]which is trivially true as \[q-1=\frac{q-1}{q-2}\cdot \frac{q-2}{q-3}\cdots\frac 32\cdot\frac 21\]thus completing the problem.

Let $S$ be the set of the red numbers. Take $x\in S$ such that $d=\gcd(x,n)$ is maximal. Claim: $S$ leaves distinct remainder when each element is divided by $\tfrac nd$. Proof: If $a\equiv b\pmod{\tfrac nd}$ for some $a,b\in S$, then $n\mid x(a-b)$, therefore $a=b$ by the problem's condition. $\blacksquare$ Call a prime $p$ tasty iff $p>d$ and $p\mid\tfrac nd$. Let $T$ denote the set of tasty primes. We claim the following. Claim: Any tasty prime $p$ cannot divide any element in $S$. Proof: If $p\mid a$, then $\gcd(a,n)\geq p > d$, contradiction to maximality. $\blacksquare$ From the two claims above, we deduce that (by projecting each element of $S$ into its remainder when divided by $\tfrac nd$) \begin{align*} |S| &\leq \#\left\{1\leq k\leq \frac nd : \text{no tasty prime } p\mid k\right\} \\ &= \frac{n}{d} \cdot \prod_{p\in T} \left(1-\frac 1p\right) \qquad (\text{by P.I.E.})\\ &= \frac{\varphi(n)}{d} \cdot \prod_{\substack{p\mid n \\ p\notin T}} \frac{p}{p-1} \\ &\leq \frac{\varphi(n)}{d}\cdot \prod_{p\leq d} \frac{p}{p-1} \\ &\leq \frac{\varphi(n)}{d} \cdot \frac{2}{1}\cdot \frac{3}{2} \cdots \frac{d}{d-1} \\ &= \varphi(n) \end{align*}so we are done.