Dividing zero

Number Theory Level 4

When working modulo some number n we call two integers divisors of zero if their product is 0. For example, 2 and 3 are divisors of zero when working modulo 6. So are 4 and 3 ( $3 \times 4=12 \equiv 0 \pmod{6} )$ . Thus, there are 3 zero divisors when working modulo 6: 2, 3, and 4.

How many zero divisors exist when working modulo 8192?

The answer is 4095.

2 solutions

Maggie Miller
Aug 2, 2015

A number $n$ is a zero divisor modulo 8192 if gcd( $8192,n)\neq1$ and $8192$ doesn't divide $n$ .

Therefore, the number of zero divisors of 8192 is $8192-1-\phi(8192),$ where $\phi$ is the Euler totient function.

Since $8192=2^{13}$ , $\phi(8192)=8192\left(1-\frac{1}{2}\right)=4096$ .

Then the answer is $8192-1-4096=\boxed{4095}$ .

Bill Bell
Aug 6, 2015

Since $8192={ 2 }^{ 13 }$ the divisors of zero must consist of all the even numbers in the set $\left\{ 1...8191 \right\}$ .