This work presents a reduced order model for gradient based aerodynamic shape optimization. The solution of the fluid Euler equations is converted to reduced Newton iterations by using the Least Squares Petrov-Galerkin projection. The reduced order basis are extracted by Proper Orthogonal Decomposition from snapshots based on the fluid state. The formulation distinguishes itself by obtaining the snapshots for all design parameters by solving a linear system of equations. Similarly, the reduced gradient formulation is derived by projecting the full-order model state onto the subspace spanned by the reduced basis. Auto-differentiation is used to evaluate the reduced Jacobian without forming the full fluid Jacobian explicitly during the reduced Newton iterations. Throughout the optimisation trajectory, the residual of the reduced Newton iterations is used as an indicator to updatethe snapshots and enrich the reduced order basis. The resulting multi-fidelity optimisation problem is managed by a trust-region algorithm. The ROM is demonstrated for a subsonic inverse design problem and for an aerofoil drag minimization problem in the transonic regime. The results suggest that the proposed algorithm is capable of aerodynamic shape optimization while reducing the number of full-order model queries and time to solution with respect to an adjoint gradient based optimisation framework.