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
Parametrices of Elliptic Equations
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.