0
$\begingroup$

let $p$ and $q$ be relatively prime then find how many positive integers less than $pq$ exists which are relatively prime to $pq$

I'm not good at such questions. Answer seems to be $(p-1)(q-1)$ but couldn't get why. Any help?

$\endgroup$
1
$\begingroup$

Hint:

By Gauß' lemmma, an integer is coprime with $pq$ if and only if it is coprime with each.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.