I will recount the more general statement of linear independence of characters, given in Lang's Algebra book, and credited to Artin. Let $G$ be a group, and $K$ a field. Then distinct homomorphisms $\phi_1, \ldots, \phi_n: G \to K^\times$ are linearly independent.
Proof: Suppose not, and suppose we have a nontrivial linear relation
$$a_1 \phi_1 + \ldots + a_n \phi_n = 0,\qquad (1)$$
where $n$ is taken as small as possible. Clearly $n>1$ and $a_i \neq 0$ for all $i$. Because the $\phi_i$ are distinct, we can find an element $g \in G$ such that $\phi_1(g) \neq \phi_2(g)$. We have
$$a_1 \phi_1(gh) + a_2 \phi_2(gh) + \ldots + a_n \phi_n(gh) = 0$$
for all $h \in G$; by virtue of the $\phi_i$ being homomorphisms, this may be rewritten to say
$$a_1 \phi_1(g)\phi_1 + a_2 \phi_2(g)\phi_2 + \ldots + a_n \phi_n(g)\phi_n = 0, \qquad (2)$$
Dividing $(2)$ by $\phi_1(g)$ and then subtracting (1) from the result $(1)$, we arrive at a nontrivial linear relation
$$\left(a_2 \frac{\phi_2(g)}{\phi_1(g)} - a_2\right) \phi_2 + \ldots = 0$$
withwhich has fewer than $n$ summands and is nontrivial by choice of $g$, contradiction. $\Box$