Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
1  
And how can I solve that? Or can you point me in the right direction? –  Khaled Aug 19 '12 at 0:51
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.