Gauss's law for magnetism is $\vec{\nabla} \cdot \vec{B} = 0$, and I read that this implies we can write $\vec{B} = \vec{\nabla} \times \vec{A}$, for some vector potential $\vec{A}$.
I understand that having $\vec{B} = \vec{\nabla} \times \vec{A}$ implies the statement of Gauss's law. But I am having trouble proving the converse; that $\vec{\nabla} \cdot \vec{B} = 0$ implies the magnetic field must take the form $\vec{B} = \vec{\nabla} \times \vec{A}$.
My attempt: By the Helmholtz decomposition theorem (https://en.wikipedia.org/wiki/Helmholtz_decomposition), we can write any vector field $$\vec{B} = -\nabla \phi + \vec{\nabla} \times \vec{A}.$$ Then $$\vec{\nabla} \cdot \vec{B} = 0 \Rightarrow -\nabla^2 \phi = 0.$$ However, this does not imply that $\phi \equiv 0$. So why can't magnetic fields be described in terms of some vector potential $\vec{A}$ but also some scalar potential $\phi$ that has $0$ Laplacian?
I don't think this has anything to do with the existence of a magnetic monopole or not, since I'm taking $\vec{\nabla} \cdot \vec{B} = 0$, but I may also be wrong.