Suppose prime number $p$ and an arbitrary number $r$ is given. What methods do you know for detection that $r$ is divisible by $p$?
Divisibility by prime numbers
0
$\begingroup$
number-theory
-
0So 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
-
0So lets say that I am wondering if $11313559|45254236$. Method: http://www.wolframalpha.com/input/?i=factor+45254236 . Answer: yes – 2012-10-07
-
0But 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
-
0In that case, division is the way to go, unless $r$ is so huge that it can't be computed explicitly. – 2012-10-07
-
0I want a general algorithm – 2012-10-07
-
0$e^{i2\pi r/p }=1$ – 2012-10-07
-
0http://en.wikipedia.org/wiki/Division_algorithm – 2012-10-07
-
0Wreza, what's not general about division? – 2012-10-07
-
0Wreza, I made a couple of edits in your question. I hope I interpreted your meaning correctly. – 2012-10-07