I was able to find the right reference. This construction is present in the book "Introduction to pseudo-differential and Fourier Integral volume 1" by J.F. Treves. More specifically the sections are as follows

1.  Parametrices of Elliptic Equations

2.  Definition and Continuity of the "Standard" Pseudodifferential Operators
in  an Open Subset of Euclidean Space. Pseudodifferential Operators  Are
Pseudolocal 

up to page 12, there is the following result:

*Lemma (2.2)*.  Let $P$ denote a differential operator with variable coefficients in $\Omega$. Suppose that there is a very $K: \mathcal{E}'(\Omega) \longrightarrow \mathcal{D}'(\Omega)$ regular operato such that $KP-I$  is  regularizing (which is sometimes expressed by saying that $K$ is a left parametrix of P). Then $P$ is  hypoelliptic, i.e., it has the following  property: Given any open set $U$ of $\Omega$, then every distribution $u$ in $U$ such that $Pu \in C^{\infty}(U)$ is a $C^\infty$ function in $U$.

The theory of pseudo-differential operators is not necessary, in fact this construction is a particular introduction to it.