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.

How to find the Number of divisors of a number 'n' that are also divisible by another number 'k' without looping through all the divisors of n? I tried the following:

Stored powers of all prime factors of n in an associative array A and did similarly for k, stored the powers of all primes factors in array B.

    ans = 1
    for a in A:    // Here a is the prime factor and A[a] gives its power
        ans *= if( a is present in B ) ? 1 : A[a] + 1
    print ans

Note : It is not homework.

share|improve this question
    
You want divisors $d$ of both $n$ and $k$. Consider what $\gcd(n,k)$ means, and its relationship to each such $d$. Calculating the $\gcd$ is fairly quick. –  Kirk Boyer Sep 3 '12 at 22:30
    
@Kirk, I think sabari wants $k$ dividing $d$, not $d$ dividing $k$. –  Gerry Myerson Sep 3 '12 at 23:22
    
Hm.. from the code he provided I got the impression otherwise (A being the prime-power factors of $n$ and B being the prime-power factors of $k$), although to be honest I don't entirely follow the code, as it is in an unfamiliar language for me. @sabari, can you clarify? –  Kirk Boyer Sep 3 '12 at 23:56
    
@KirkBoyer Yeah, Gerry is right. I want the divisors of n that are divisible by k. That is k dividing d. –  sabari Sep 4 '12 at 7:40
add comment

2 Answers

up vote 5 down vote accepted

Any divisor of $n$ that is itself divisible by $k$ can be written as $d k$, where $d$ is a divisor of $\frac nk$. Hence their number is exactly the number of divisors of $\frac nk$.

Of course we need $k$ to be a divsor of $n$ for this to make sense at all.

share|improve this answer
    
Thanks a lot! I understood the mistake I made. Out of curiosity , may I ask a small variant of the above.. is it possible to find the "number of divisors of n which are not divisible by k" by simple methods? –  sabari Sep 4 '12 at 7:57
    
I got the idea for the above variant also. –  sabari Sep 4 '12 at 8:20
add comment

All you have to do is compute $\sigma_0(n/k)$, where $\sigma_0(m)$ is the divisor function, which counts the number of divisors of $m$. The reason of this is that $$ k \, | \, m \, | \, n \quad \Longleftrightarrow \quad m = kd \quad \text{and} \quad d \, | \, n/k. $$ This is quite easy to prove, I'll leave it up to you. Now to compute $\sigma_0(n/k)$, one can show that $\sigma$ is a multiplicative function, because $f(n) = 1$ is multiplicative, hence $$ \sigma_0(n) = \sum_{d \, | \, n} f(d) $$ also is (well-known theorem in number theory that $\sum_{d \, | \, n} f(d)$ is multiplicative when $f$ is). Therefore, since $\sigma_0(p^{\alpha}) = \alpha+1$, you have $$ \sigma_0(n) = \prod_{p \, | , n} (\alpha(n,p) + 1) $$ where $\alpha(n,p)$ stands for the greatest power of $p$ dividing $n$. In other words, all you have to do is factor $n/k$ and use the factorization to compute $\sigma_0(n/k)$.

Hope that helps,

share|improve this answer
    
$\sigma$ is usually used for the sum of the divisors; $\tau$ or $d$ for the number of divisors. –  Gerry Myerson Sep 3 '12 at 23:23
    
Right ; I forgot to write $\sigma_0$. The function $\sigma_k$ is usually for the sum of the $k^{\text{th}}$ powers. Thanks for noticing. –  Patrick Da Silva Sep 4 '12 at 2:55
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.