Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.