Let $\phi$ denote Euler's totient function, and $p, q > 1$ be primes. Conjecture and prove a formula for $\phi(pq)$ in terms of $p$ and $q$.

Sure, here is the conjecture and proof:

Conjecture: For any two primes p and q, the Euler's totient function φ(pq) = (p-1)(q-1).

Proof:

By definition, Euler's totient function φ(n) counts the positive integers less than n that are relatively prime to n.

Since p and q are primes, they have no common factors other than 1. Therefore, the numbers less than pq that are not relatively prime to pq are multiples of p and multiples of q.

There are q multiples of p less than pq (namely p, 2p, 3p, ..., qp), and p multiples of q less than pq (namely q, 2q, 3q, ..., pq). However, pq itself is counted twice, so we subtract one to correct this.

Therefore, the total number of integers less than pq that are not relatively prime to pq is p + q - 1.

Since there are pq total integers less than pq, the number of integers that are relatively prime to pq is pq - (p + q - 1) = (p-1)(q-1).

Therefore, φ(pq) = (p-1)(q-1). This completes the proof.