0
$\begingroup$

Suppose prime number $p$ and an arbitrary number $r$ is given. What methods do you know for detection that $r$ is divisible by $p$?

  • 0
    So you try to divide $r$ by $p$ ... ?2012-10-07
  • 0
    @Thomas and you have to check whether what you got is an algebraic integer, if you're not in $\mathbb Q$ but in some larger algebraic field. But it's not clear if this is what Wreza asks for...2012-10-07
  • 0
    @tohecz: ahh ok, I was thinking that something deeper was going on.2012-10-07
  • 0
    So lets say that I am wondering if $11313559|45254236$. Method: http://www.wolframalpha.com/input/?i=factor+45254236 . Answer: yes2012-10-07
  • 0
    But as I say, I'm not sure whether this is what is asked. If so, it is not an easy task: You easily get some polynomial with root $r/p$ if you know minimal polynomials of $p$ and $r$, but you need to find the minimal one for $r/p$ which is a complicated task.2012-10-07
  • 0
    $r$ is integer and discussion about integer numbers.2012-10-07
  • 0
    In that case, division is the way to go, unless $r$ is so huge that it can't be computed explicitly.2012-10-07
  • 0
    I want a general algorithm2012-10-07
  • 0
    $e^{i2\pi r/p }=1$2012-10-07
  • 0
    http://en.wikipedia.org/wiki/Division_algorithm2012-10-07
  • 0
    Wreza, what's not general about division?2012-10-07
  • 0
    Wreza, I made a couple of edits in your question. I hope I interpreted your meaning correctly.2012-10-07

2 Answers 2