Of course, it's not true what you want to prove, and it's very important in the connection with electrodynamics, because it's basically what's behind gauge invariance, which is the most important concept of electrodynamics to begin with. So let's think about the electromagnetic potentials carefully again:
Observable is the electromagnetic field. In the usual 3D formalism it's described by the electric and magnetic fields ##\vec{E}## and ##\vec{B}##. There are two sets of Maxwell equations, the homogeneous ones, which are constraints to the fields, not involving the sources ##\rho## (charge density) and ##\vec{j}## (current density). For sake of convenience I use Heaviside-Lorentz units, in which ##\vec{E}## and ##\vec{B}## have the same dimensions as it should be from a relativistic point of view:
$$\vec{\nabla} \times \vec{E}+\frac{1}{c} \partial_t \vec{B}=0, \quad \vec{\nabla} \cdot \vec{B}=0.$$
These constraints can be fulfilled identically by introduction of the potentials, which however are not unique, as we shall see soon.
Indeed, Helmholtz's fundamental theorem of vector calculus says the from ##\vec{\nabla} \cdot \vec{B}=0## it follows that there exists a vector potential such that
$$\vec{B}=\vec{\nabla} \times \vec{A},$$
and it's immediately clear that ##\vec{A}## is not uniquely defined by ##\vec{B}##, because any other vector potential
$$\vec{A}'=\vec{A}-\vec{\nabla} \chi$$
with an arbitrary scalar field ##\chi## leads to the same ##\vec{B}##, because
$$\vec{\nabla} \times \vec{A}' = \vec{\nabla} \times \vec{A} + \vec{\nabla} \times \vec{\nabla} \chi=\vec{\nabla} \times \vec{A}=\vec{B}.$$
Now we use ##\vec{B}=\vec{\nabla} \times \vec{A}## in the other homogeneous Maxwell equation (Faraday's Law of induction):
$$\vec{\nabla} \times \vec{E}+\frac{1}{c} \vec{\nabla} \times \partial_t \vec{A}=0$$
or
$$\vec{\nabla} \times \left (\vec{E} + \frac{1}{c} \partial_t \vec{A} \right)=0.$$
This implies that the expression in the bracket is derivable from a scalar potential ##\Phi##,
$$\vec{E}+\frac{1}{c} \partial_t \vec{A}=-\vec{\nabla} \Phi$$
or
$$\vec{E}=-\frac{1}{c} \partial_t \vec{A}-\vec{\nabla} \Phi.$$
Of course, for a given ##\vec{E}## the scalar potential ##\Phi## depends on the choice of ##\vec{A}##. Since ##\vec{E}## is observable and thus must be uniquely defined, ##\Phi## must change when changing ##\vec{A}## using the gauge field ##\chi##:
$$\vec{E}=-\frac{1}{c} \partial_t \vec{A}' - \vec{\nabla} \Phi'.$$
Now
$$\vec{E}=-\frac{1}{c} \partial_t (\vec{A}-\vec{\nabla} \chi) - \vec{\nabla} \Phi' = -\frac{1}{c} \partial_t \vec{A} - \vec{\nabla} \left (\Phi'- \frac{1}{c} \partial_t \chi \right),$$
which implies that the gauge transformation for the scalar potential is
$$\Phi=\Phi'-\frac{1}{c} \partial_t \chi \; \Rightarrow \; \Phi'=\Phi+\frac{1}{c} \partial_t \chi.$$
Due to this gauge invariance of the entire formalism under gauge transformations of the potentials
$$\Phi'=\Phi+\frac{1}{c} \partial_t \chi, \quad \vec{A}'=\vec{A}-\vec{\nabla} \chi$$
the potentials ##\Phi## and ##\vec{A}## are not uniquely determined but only up to such a gauge transformation.
To see how this is consistent with the inhomogeneous Maxwell equations,
$$\vec{\nabla} \times \vec{B}-\frac{1}{c} \partial_t \vec{E}=\frac{1}{c} \vec{j}, \quad \vec{\nabla} \cdot \vec{E}=\rho,$$
we note that this equations imply the equation of continuity, i.e., the local form of charge conservation. Indeed taking the divergence of the first equation (the Ampere-Maxwell Law) and using the second equation (Gauss's Law for the electric field) leads to
$$-\frac{1}{c} \partial_t \vec{\nabla} \cdot \vec{E}=-\frac{1}{c} \partial_t \rho = \frac{1}{c} \vec{\nabla} \cdot \vec{j} \; \Rightarrow \; \partial_t \rho + \vec{\nabla} \cdot \vec{j}=0.$$
Now plugging in the potentials in the inhomogeneous equations leads to
$$\vec{\nabla} \times (\vec{\nabla} \times \vec{A}) + \frac{1}{c^2} \partial_t^2 \vec{A} + \frac{1}{c} \vec{\nabla} \partial_t \Phi=\frac{1}{c} \vec{j}, \quad \frac{1}{c} \partial_t \vec{\nabla} \cdot{\vec{A}} + \Delta \Phi=-\rho.$$
Since now the potentials are only determined up to a gauge transformation, i.e., up to an arbitrary scalar field ##\chi## we can impose one constraint, a socalled gauge-fixing condition. A very convenient choice is the Lorenz gauge condition,
$$\frac{1}{c} \partial_t \Phi+\vec{\nabla} \cdot \vec{A}=0.$$
Plugging this into the above equations leads to
$$\left (\frac{1}{c^2} \partial_t^2 - \Delta \right) \vec{A}=\frac{1}{c} \vec{j}, \quad \left (\frac{1}{c^2} \partial_t^2 - \Delta \Phi \right)=\rho.$$
In the first equation we have used the identity
$$\vec{\nabla} \times (\vec{\nabla} \times \vec{A})=\vec{\nabla}(\vec{\nabla} \cdot \vec{A})-\Delta \vec{A}$$
and the Lorenz gauge condition. In the 2nd equation we just used the gauge condition. This procedure shows that the Lorenz gauge condition decouples the equations for the scalar and vector potentials in 4 wave equations for each of these four field degrees of freedom, ##\Phi## and the three Cartesian components of ##\vec{A}##.
Now it's easy to see that the Lorenz gauge condition is consistent with these wave equations thanks to the continuity equation for ##\rho## and ##\vec{j}##. This shows that the Maxwell equations are gauge invariant when formulated in terms of the potentials.
One can show this equivalence also for other gauge fixing conditions, e.g., the sometimes also convenient Coulomb gauge, which reads
$$\vec{\nabla} \cdot \vec{A}=0.$$
One can show again that thanks to the continuity equation for ##\rho## and ##\vec{j}## the resulting equations for ##\Phi## and ##\vec{A}## are compatible with this gauge condition either. One can also show that the Lorenz-gauge potentials are related with the Coulomb-gauge potentials by a gauge transformation:
https://arxiv.org/abs/physics/0204034
