Why curl free field implies existence of potential function?

For $\mathbb{R}^{3}$, Stokes' Theorem is the key, which is probably where you are working. Start with the simplest case where you have a vector field $\vec{F}$ defined on all of $\mathbb{R}^{3}$, and suppose that the components of $F$ are continuously differentiable. Then, if $\nabla\times \vec{F}=0$ throughout $\mathbb{R}^{3}$, Stokes' theorem tells you that $\oint_{C}\vec{F}\cdot d\vec{l}=0$ for all simple, closed curves $C$, because you can trade that integral for an integral over any smooth, orientable surface patch $S$ whose boundary is $C$--specifically, Stokes' Theorem gives you $$ \int_{C}\vec{F}\cdot d\vec{l} = \int_{S}\nabla\times \vec{F}\cdot d\vec{S} = 0. $$ So you can define a scalar function $\phi$ by $$ \phi(\vec{x}) = \int_{0}^{\vec{x}}\vec{F}\cdot d\vec{l}, $$ and a specific path need not be mentioned. This is because the difference of two integrals along different paths gives you a closed path integral, which is 0 by Stokes' Theorem. There are details to be covered, for sure, especially in the generality of paths, but that's the basic idea. The end result is a scalar function $\phi$ whose value is defined by any smooth path you choose from $\vec{0}$ to $\vec{x}$. That's really the definition of a potential function such as the Newtonian or Coulomb potential: it is a path integral of the inverse-square vector force law along a path from a reference (ground) to some other point $\vec{x}$, and the path doesn't matter.

Knowing you have the freedom to choose any path, by choosing paths wisely, it's not that hard to show that $\nabla \phi = \vec{F}$. For example, if you fix $y=y_{0}$ and $z=z_{0}$, and allow $x$ to vary, you can choose a convenient path of a straight line to evaluate the following: $$ \phi(x,y_{0},z_{0})-\phi(x_{0},y_{0},z_{0})=\int_{(x_{0},y_{0},z_{0})}^{(x,y_{0},z_{0})}\vec{F}\cdot d\vec{l}. $$ The resulting integral on the straight line is $$ \phi(x,y_{0},z_{0})-\phi(x_{0},y_{0},z_{0})=\int_{x_{0}}^{x}F_{1}(x',y_{0},z_{0})\,dx' $$ where $\vec{F}=(F_{1},F_{2},F_{3})$. From the above it's really easy to see from the fundamental theorem of Calculus that $$ \frac{\partial \phi}{\partial x} = F_{1}. $$ Similarly, $$ \nabla \phi = (\frac{\partial \phi}{\partial x},\frac{\partial \phi}{\partial y},\frac{\partial \phi}{\partial z}) = (F_{1},F_{2},F_{3})= \vec{F}. $$ For more general domains with obstacles, you have to be more careful about the paths you allow to be chosen. Essentially, you want only to allow paths such that the differences of path integrals allows one to apply Stokes' theorem on the resulting closed path.

For example, if $F$ is defined on $\mathbb{R}^{3}$, except for an infinite cylinder, then closed paths circling the cylinder might not give you zero because $F$ is not defined on any surface you'd have to use with Stokes' Theorem. So, if you add a slit (half-infinite plane) through the center line of the cylinder, and don't allow paths to cross that slit when defining $\phi$, then you're still okay: any path from the reference point (ground) to another point $\vec{x}$ which stays in the slitted region will give you the same definition of $\phi$ because Stokes' Theorem applies to the difference of two different integrals along such paths. It may be that $\phi$ takes a jump across the slit, which is what you get with branch cuts in Complex Analysis. Things like that can supposedly happen in Electromagnetics, too.