*Posted by Seungln in : potd , trackback
*
Let $V(x)$ be the possible number of positive integers $n$ such that $n^{-1}$ in modulus $x$ exists – that is, there exists an integer r such that $n \equiv \frac{1}{r} \pmod{x}$. Find $p$ such that $V(1998)\equiv p \pmod{330}$

show

For an integer $n$ to have an inverse in modulus $x$, it is necessary that $n$ not be a non-trivial divisor of $x$ – that is, a divisor of $x$ that isn’t 1. This means that $n$ and $x$ must be relatively prime. Therefore, we see that $V(x)$ is simply $\phi(x)$ in disguise, where $\phi(x)$ is Euler’s Totient Function.

Therefore, $V(1998) = \phi(1998) = 1998 (1-\frac{1}{2}) (1 – \frac{1}{3}) (1 – \frac{1}{37}) = 1998 \frac{1}{2} \frac{2}{3} \frac{36}{37} = 648$

$648 \equiv \boxed{318} \pmod{330}$

## Comments»

no comments yet - be the first?