

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Given the positive integer $n$, for which integers values of $x$ will the equation below be satisfied?

$$nx \equiv 0\pmod{(x-n)}$$

Also, how many positive integers $x$ exist for a given $n$?

share|cite|improve this question
What you want is to find $x$ such that $nx=\alpha (x-n)$ has an integer solution in $\alpha$. You can solve $x(\alpha-n)=\alpha n$. – Sigur Aug 19 '12 at 0:29
And how can I solve that? Or can you point me in the right direction? – Khaled Aug 19 '12 at 0:51
up vote 1 down vote accepted

Since $x\equiv n$ modulo $x-n$ we have the logical equivalence (same modulus)

$$nx\equiv 0 \iff n^2\equiv 0\iff (x-n)\mid n^2.$$

Thus there is a correspondence $x-n\leftrightarrow d$ for solutions $x$ and divisors $d\mid n^2$. We conclude that the solution set is given in terms of $n$ by $x\in\{n+d:d\mid n^2\}$ (negative divisors also included). It follows that the number of solutions is $2\,\sigma_0(n^2)$ (see divisor sigma). If we restrict our attention to positive moduli only then we ignore the negative divisors of $n^2$, and the solution count is instead $\sigma_0(n^2)$.

share|cite|improve this answer

You want $(a-n) | an$. Let $d = gcd(a, n)$, $A = a/d$, and $N = n/d$, so $(A, N) = 1$.

Rewriting, $d(A-N) | d^2AN$ or $(A-N)|dAN$. Since $(A, N) = 1$, $(A-N,A) = (A-N, N) = 1$, so $(A-N) | d$.

This is now turned into an algorithm.

Since $d = gcd(a, n)$, $d | n$. Let $d$ go through all the divisors of $n$; for each $d$, let $N = n/d$. Since $(A-N) | d$, for each divisor $k$ of $d$, let $A-N = k$. or $A = N+k$. Finally, $a = Ad = d(N+k) =n+kd$.

As a check, $\frac{an}{a-n} = \frac{n(n+kd)}{kd} = \frac{n^2}{kd}+n$ and this is an integer since $d | n$ and $k | d $.

To get a formula for the number of results, counting 1 for each item found in the algorithm's inner loop, I get $\sum_{d|n} \sum_{k|d} 1 = \sum_{d|n} \tau(d)$, where $\tau(m)$ is the number of divisors of $m$.

This probably can be simplified further (since $\tau$ is multiplicitive), but I am tired now and this is off the top of my head. I may get back to this later.

share|cite|improve this answer

Your Answer


