[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/session.php on line 1042: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4786: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4788: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4789: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4790: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
BdMO Online Forum • View topic - $x^2 \equiv x (mod n)$

$x^2 \equiv x (mod n)$

For discussing Olympiad Level Number Theory problems

$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
dshasan

Posts: 66
Joined: Fri Aug 14, 2015 6:32 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$.
Frankly, my dear, I don't give a damn.

Posts: 147
Joined: Mon Mar 28, 2016 6:21 pm