Probability

Here are the first 6 primes: $\{2,3,5,7,11,13\}$

We can take a look at all the possibilities by making a table. 

$\begin{matrix}&\color{blue}2&\color{blue}3&\color{blue}5&\color{blue}7&\color{blue}11&\color{blue}13\\\color{red}2&4&5&7&\color{magenta}9&13&\color{magenta}15\\\color{red}3&5&\color{magenta}6&8&10&14&16\\\color{red}5&7&8&10&\color{magenta}12&16&\color{magenta}18\\\color{red}7&\color{magenta}9&10&\color{magenta}12&14&\color{magenta}18&20\\\color{red}11&13&14&16&\color{magenta}18&22&\color{magenta}24\\\color{red}13&\color{magenta}15&16&\color{magenta}18&20&\color{magenta}24&26\end{matrix}$

Blue numbers and red numbers represent the number that Paul chose and the number that Jesse chose respectively.

Pink numbers are those divisible by 3.

By trial-and-error, out of all 36 possible cases, 13 cases has a sum divisible by 3.

Therefore, 

$\text{Prob}(\text{sum divisible by 3}) = \dfrac{13}{36}$

Assuming they can pick the same number

36 choices

2 7

2 13

5 7

5 13

7 11

3 3              the red ones can be reversed      11 choices out of 36

OOps...I see from Max answer I missed   11 13      13 11     so the answer would be the same    13 /36          (Thanx, max!)