Is there a way to find whether a number (say $A$) formed by summing powers of another number (say $B$) is divisible by another number $C$? $A$ is a number like, for example, $B^1+B^3$. We can use a power of $B$ at most one time.

I don't want to know the number $A$. I just want to know that is $A$ is divisible by $C$.

Any help is appreciated.

edit: i found out that the answer is always yes :D

  • $\begingroup$ that is, for example A can not be B^2+B^2. i just can include B^2 once. or i don't include it at all $\endgroup$ – bliss Sep 11 '11 at 10:00
  • $\begingroup$ but if there is not such a number i will do infinitely many calculations. i dont want to know that if a number is divisible by C. i want to know that can i write a number formed from sums of powers of B that is divisible by C. i want to answer the question that is there a number A? $\endgroup$ – bliss Sep 11 '11 at 12:11
  • 1
    $\begingroup$ Having shared your question with us, and having found an answer to your question, maybe you want to share your answer with us? $\endgroup$ – Gerry Myerson Sep 11 '11 at 13:32

If B and C are coprime, $B^{\phi(c)}=1 \pmod C$, where $\phi(n)$ is Euler's totient function. In this case there is always such an A, take $\sum_{i=1}^CB^{i\phi(C)}$. If they are not coprime I believe you can do this with the $B/gcd(B,C)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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