$x^2 \equiv x (mod n)$
Let $n$ be a positive integer. Determine, in terms of n, the number of $x$ such that $x \in {1,2,...n}$ and \[x^2 \equiv x(mod n)\]
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.
- Charles Caleb Colton
- Charles Caleb Colton
- ahmedittihad
- Posts:181
- Joined:Mon Mar 28, 2016 6:21 pm
Re: $x^2 \equiv x (mod n)$
If we denote $f(n)$ the desired number, then CRT implies $f(mn)=f(m)f(n)$ whenever $(m;n)=1$.
So it suffices to find $f(n)$ when $n$ is a prime power.
It's quite trivial that there are $2$ solutions for $x $ if $n $ is a prime power. So, the answer is $2^z $ where $z $ is the number of distinct primes in the prime factorization of $n $.
So it suffices to find $f(n)$ when $n$ is a prime power.
It's quite trivial that there are $2$ solutions for $x $ if $n $ is a prime power. So, the answer is $2^z $ where $z $ is the number of distinct primes in the prime factorization of $n $.
Frankly, my dear, I don't give a damn.