$Mod\ 3\rightarrow remainders: 0,1,2$
$Mod\ 5\rightarrow remainders: 0,1,2,3,4$
$Total\ pairs\rightarrow 5\times 3=15$
$(0,0),(0,1),(0,2)...,(2,0),(2,1)...,(2,4)$
Now pick any two pairs $(a,b)\&(c,d)$ and try to satify $a\equiv cmod3\ \&\ b\equiv dmod5.$
None of these pairs will satify this condition, that's why we will go out and find a new pair that can satify our need.
Question asked for minimum and hence we will welcome only a single pair into our team of already 15 pairs.
$\therefore 15+1=16\ pairs\ in\ total$