You are on the right track thinking of how potential energy is dependent only on position. you have to be careful, though, to avoid circular reasoning in defining potential energy -- i.e., you can't just assume it is the function whose negative gradient gives the force.
The existence of a scalar potential $\Phi$ such that $\mathbf{F} \propto \nabla \Phi$ follows from the converse of the gradient theorem: Because line integrals of $\mathbf{F}$ are path-independent (equivalently potential energy depends only on position), such a $\Phi$ exists.
In the more general language of differential geometry, this follows from the Poincaré lemma. The differential form corresponding to $\mathbf{F}$ is closed; its exterior derivative (equivalent to the curl in three dimensions) vanishes. As long as your space is contractible (basically there are no topological problems preventing arbitrary loops from being smoothly shrunk to a point), the Poincaré lemma says all closed forms are exact. That is, the differential form corresponding to $\mathbf{F}$ is itself the exterior derivative of something, which must be a scalar by dimension counting. The exterior derivative of a scalar is essentially its gradient. That is,
\begin{align}
\mathrm{d} f & = 0 && \Longrightarrow & f & = \mathrm{d}\phi && \text{(Poincare lemma)} \\
\nabla \times \mathbf{F} & = 0 && \Longrightarrow & \mathrm{F} & = \nabla\Phi && \text{(gradient theorem converse).}
\end{align}
