magnetic field with a gradient? Usually it is said that the Maxwell equation $\vec \nabla \cdot \vec{B}=0$ is solved by introducing the vector potential according to $\vec B=\vec \nabla \times \vec A$.
However, I supose that one could write the more general decomposition $\vec B=\vec \nabla \times \vec A+\vec \nabla f$ and require $\nabla^2 f=0$ to enforce $\vec \nabla \cdot \vec{B}=0$.
Why is this never done? Why must magnetic fields be purely rotational?
 A: There's that other Maxwell equation,
$$ \nabla \times B = J + \dot{E}. $$
If you take $B$ to have a gradient component $\nabla f$, it makes no contribution to this equation either, so adding a $\nabla f$ to $B$ that satisfies $\nabla^2 f = 0$ does not affect the dynamics at all (much as adding a $\nabla \Lambda$ to $A$ doesn't affect $B$ at all).
But there are cases where one does take a scalar potential: if the system is static (no current, no changing fields), then we can work with a magnetic scalar potential. See also this phys.se question.
I think the real answer to your question is the Helmholtz decomposition: given a vector field $F$, one can prescribe a unique decomposition $F = -\nabla \Psi + \nabla \times A$, where $\Psi$ is given by
$$ \Psi(x) = \int_V G(x;x') \nabla \cdot F(x') \, dx' - \int_{\partial V} G(x;x')n' \cdot F(x') \, dS', $$
where $G(x;x') = 1/(4\pi |x-x'|)$ is the Green's function for the (scalar) Laplacian. For the magnetic field the first term vanishes, of course. This solution is unique because solutions to Laplace's equation are unique.
A: Nice question. I've never seen that way. You are mathematically right and physically not wrong, but not right "too" (maybe a superposition of quantum states :). The two points here are $\vec B$ being purely rotational and the, say, "gauge plus invariance". The first law for $\vec B$, $\nabla·\vec B=0$ sets the point: "purely rotational" means "zero divergence". The second is more or less the same. The vector potential is defined this way, as the (not unique) vector field the rotational of wich is the magnetic field. So is, that is the definition of $\vec A$, not the definition of $\vec B$. Incidentally, the Helmholtz decomposition is invoked to guarantee the existence of such field, not to supplement the definition of $\vec A$ with some other field. So, you'll never see anything more than $\nabla\times\vec A$.
About the possibility of other definitions for auxiliar fields, we have to consider the physical meaning that can be bestowed to these fields or any other surplus. Originally, the vector potential had not physical meaning at all, being a useful definition to simplify many calculations. Later, the usefulness of the vector potential seemed to be complemented by some physical meaning, revealed or suggested by some experiments in the context of quantum mechanics. I don't see (I don't mean "it haven't") any relevance for that $f$ supplementing the definition of $\vec A$ to get $\vec B$.
The question is reminiscent of that about the "definition" of force. It is given in really as definition, leading this fact sometimes to the discussion about if it can be any definition and all work fine or not. Or some discussions about the famous paper by Einstein, where he defines the frame of reference and from here it seems that all the point about Special Relativity is some (contingent?) definitions.
