How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$ Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form? 

This is actually a homework problem with a hint that if a $n = p^a$$q^b$ then exactly half of the elements in $Z_n$ with jacobi symbol +1 are quadratic residues mod n and we assume that initially verifier knows a quadratic non-residue x with jacobi symbol +1.  

I stuck there because it seems extremely difficult to convince Verifier that n is of given form. It is not simply like after Verfier sends a challenge number to Prover and Prover shows that he knows the fact that if the challenge number is QNR or QR. For me to convince Verfier all jacobi +1 elements have to be generated in $Z_n$ and Prover has show that exactly half of them are QR. (Assume that Verifier can generate with x itself thus it does not violate Zero knowledge. But I am not sure if it is easy(polynomial time consuming) to generate all Jacobi +1 elements yet. Well it is true that if we let $z = r^2$ for a randomly picked r from $Z_n$ then $y = r^2x$ is also a QNR with jacobi symbol +1... So finding another QNR with jacobi symbol +1 is easy for verifier... ) But To show "exactly half" then Prover will need to show which one is QR and which is are QNR then it will violate Zero knowledge property since V is not suppose know that. But any other way to show "exactly half"?

Any hint or help is greatly appreciated. Thanks!
Actually, it is not necessary for the prover to show that "exactly half" of elements with Jacobi symbols being +1 are, in fact, QR.  Instead, here are some hints:


Assuming that n is not of that form (and also n is not of the form $n = p^a$, which is easy test for), the probability that a random element with Jacobi symbol +1 is a QR is at most $q$ (homework assignment for you: what is the value of $q$)
If we get a value $x$ from the verifier which is a QR, how can we show in a zero knowledge way that $x$ is a QR (with probability $> 1 - \delta$)?
If the provider gives us a series of random $x$'s, and we either respond to each $x$ with 'not a QR', or 'it's a QR; here's the zero knowledge proof with probability $> 1 - \delta$', how many trials with random elements would be needed before the verify can conclude (with probability $> 1 - \epsilon$) that the fraction of Jacobi symbol +1 elements which are QR are $&gt; q$?