〔詳細〕
p とq が互いに素のときは、上記２つのように考えられませんので、改めて別の作戦で進める必要があります。

例えば p＝5, q＝6 のケースで考えてみます。
ちなみに、先に答えとしては、
① φ(5)：1, 2, 3, 4 の4個
② φ(6)：1, 5 の2個
③ φ(30)：1, 7, 11, 13, 17, 19, 23, 29 で8個
という関係性です。

まず事実として確認して欲しいのが、③ で列挙した数について、
・5 で割った余りは、① の 1, 2, 3, 4 のいずれか
・6 で割った余りは、② の 1, 5 のいずれか
になっているということです。（※）

例えば、19 の場合だと、
・5 で割った余りは 4
・6 で割った余りは 1 となっています。
（最終的には、③ の各数で、この余りの組合せが全部違っていて、なので 2×4 で 8 が求まる、という方向に持っていきます）

この（※）が言える理由は、
例えば「6 で割った余りが 2（②に含まれないもの）」みたいなことが起こっているなら、n＝6×●＋2 の形式ということで、2で括れてしまいますので、「30とは互いに素ではない数（③ の中からは除外されているはず）」ということになってしまうためです。
 
 
次に、
・5 で割った余りは 4
・6 で割った余りは 1
となるのが（1以上30以下で）19 以外に存在するのか、ということを検討します。

もし、存在して、それを y とするとき、
19 も y も 5×●＋4 の形式のため、19－y は5の倍数で、
一方、19 も y も 6×■＋1 の形式のため、19－y は6の倍数でもある、ということになります。
よって、19－y は（5の倍数かつ6の倍数のため）30の倍数ということになり、
19－y＝30k（kは整数）で、
移項して y＝19－30k より、
y（≠19）は、1以上30以下の間にはないということになります。
（19に30ごと加減した数であるため）

ですので、③ に含まれる数については、
・5 で割った余りの a
・6 で割った余りの b
について、(a, b) の組合せはすべて異なることになり、
a が4通り、b が2通りということで、4×2 の8通りの組合せを考えればいいかな、ということになります。

ただ、これだけだと不十分で、
実はまだ「少なくとも、共通の (a, b) はない」ことしか言えておらず、
もしかしたら、③ の中には (a, b)＝(3, 1) みたいな組合せは無いかもしれません。
（最大で8通りとは言えるが、これよりも少ないかもしれない）
 
 
ですので、今度は逆に、(a, b)＝(3, 1) みたいな場合も含め、全8通りがきちんと③の中にあることを確認します。
これについては、
・n＝5x＋3
・n＝6y＋1
から、5x＋3＝6y＋1（つまり、－5x＋6y＝2）が得られ、これはいわゆる１次不定方程式の話になります。
この場合だと、x＝2－6k が得られ、n＝－30k＋13 となり、1≦n≦30 で n＝13 が存在する、と確認することができます。
（証明としては、これを一般化すればよい）

ですので、① の4通りと ② の2通りの積である8通りについて、漏れなくダブりなく対応する ③ の値が存在する、ということになります。
 
 
※ なお、上記では順番に説明しましたが、
p, q が互いに素のとき、
・p で割った余りが a
・q で割った余りが b
となるような数xが、1≦x≦pq に１つだけ存在することが知られていて、これを「中国剰余定理」と呼びます。