Q: A Statistic is published that 31% of people think it is okay to smoke in public. What is the smallest sample that could have been interviewed to get this result.
A: 13, with 4 "yes" and 9 "no" responses.
I can see that this answer can be obtained in a variety of ways - enumerating all sample sizes from 1 to 100; guessing; and formulating it as an Integer Programming Problem.
Of course, this generalizes to other proportions (for example, 0.4 = 2/5):
\begin{array}{llllllllll} \frac{1}{67} & \frac{1}{41} & \frac{1}{29} & \frac{1}{23} & \frac{1}{19} & \frac{1}{16} & \frac{1}{14} & \frac{1}{12} & \frac{1}{11} & \frac{1}{10} \\ \frac{1}{9} & \frac{2}{17} & \frac{1}{8} & \frac{1}{7} & \frac{2}{13} & \frac{3}{19} & \frac{1}{6} & \frac{2}{11} & \frac{3}{16} & \frac{1}{5} \\ \frac{3}{14} & \frac{2}{9} & \frac{3}{13} & \frac{4}{17} & \frac{1}{4} & \frac{5}{19} & \frac{3}{11} & \frac{5}{18} & \frac{2}{7} & \frac{3}{10} \\ \frac{4}{13} & \frac{6}{19} & \frac{1}{3} & \frac{10}{29} & \frac{6}{17} & \frac{4}{11} & \frac{7}{19} & \frac{3}{8} & \frac{7}{18} & \frac{2}{5} \\ \frac{7}{17} & \frac{5}{12} & \frac{3}{7} & \frac{4}{9} & \frac{5}{11} & \frac{6}{13} & \frac{7}{15} & \frac{10}{21} & \frac{17}{35} & \frac{1}{2} \\ \frac{18}{35} & \frac{11}{21} & \frac{8}{15} & \frac{7}{13} & \frac{6}{11} & \frac{5}{9} & \frac{4}{7} & \frac{7}{12} & \frac{10}{17} & \frac{3}{5} \\ \frac{11}{18} & \frac{8}{13} & \frac{5}{8} & \frac{7}{11} & \frac{11}{17} & \frac{19}{29} & \frac{2}{3} & \frac{13}{19} & \frac{9}{13} & \frac{7}{10} \\ \frac{5}{7} & \frac{13}{18} & \frac{8}{11} & \frac{14}{19} & \frac{3}{4} & \frac{13}{17} & \frac{10}{13} & \frac{7}{9} & \frac{11}{14} & \frac{4}{5} \\ \frac{13}{16} & \frac{9}{11} & \frac{5}{6} & \frac{16}{19} & \frac{11}{13} & \frac{6}{7} & \frac{13}{15} & \frac{7}{8} & \frac{8}{9} & \frac{9}{10} \\ \frac{10}{11} & \frac{11}{12} & \frac{13}{14} & \frac{15}{16} & \frac{18}{19} & \frac{22}{23} & \frac{28}{29} & \frac{39}{40} & \frac{66}{67} & 1 \\ \end{array}
My question is "Can the solution be expressed in "closed form" using, say, GCD and the numbers (31,69 and 100)?".
You are looking for the best rational approximation in the range $(0.305,0.315)$ where we can argue about the boundaries, but they don't matter for your example. You can form the continued fraction for $\frac {31}{100}$, then find the first approximation that is within the bounds.