One number divisible by all prime factors of another? Given two numbers $x$ and $y$, how to check whether $x$ is divisible by all prime factors of $y$ or not?, is there a way to do this without factoring $y$?.
 A: $x$ is divisible by all prime factors of $y$ if and only if for some $n$, $x^n\equiv0$ modulo $y$. You might compute $x^n$ modulo $y$ for $n=1$ up to say $\log_2(y)$ and see if $0$ arises as a result. For large numbers, where prime factorization is hard, but modular arithmetic is doable, this would be more efficient than prime factorization. I say $\log_2(y)$ because that is an upper bound for any exponent on a prime factor of $y$ in the prime factorization of $y$. So by the time you have raised $x$ to that power, any prime factor of $x$ will then be raised to a power at least as large as it could arise in the prime factorization of $y$.
@Joffan points out in the comments that you could skip to just raising to the $\log_2(y)$ power. If you use repeated squaring, it does speed things up to $\log_2\log_2(y)$ multiplications modulo $y$. In fact, raising even higher to the next power of $2$ saves a step or two here and there.
Applied to Mark's examples, this process would go like this:
$$\begin{align}
x=168,y=132&\rightarrow \lfloor\log_2(y)\rfloor=7\rightarrow\text{8 is the next power of 2}\\
&\phantom{\rightarrow \lfloor\log_2(y)\rfloor=7\rightarrow}\text{Explicitly,  $8=2^{\lceil\log_2{ \lfloor\log_2(y)\rfloor}\rceil}$}\\
&\rightarrow 168^8=((168^2)^2)^2\\
&\rightarrow 168^8\equiv(108^2)^2\\
&\rightarrow 168^7\equiv72^2\\
&\rightarrow 168^7\equiv144\\
\end{align}$$
which uses three squarings mod $y$ to determine the answer is no. And$$\begin{align}
x=168,y=98&\rightarrow \lfloor\log_2(y)\rfloor=6\rightarrow\text{8 is the next power of 2}\\
&\rightarrow 168^8=((168^2)^2)^2\\
&\rightarrow 168^8=(0^2)^2\\
&\rightarrow 168^8=0^2\\
&\rightarrow 168^8\equiv0\\
\end{align}$$
which technically uses three squarings if we don't see the early $0$ to determine the answer is yes. (Or you could make the algorithm check each step to see if there are early zeros if you like---not much time saved though by preventing a few calculations of $0^2$.)
A: If $x$ is divisible by all the prime factors of $y$, then so is the highest common factor $h_1$ of $x$ and $y$.
To test whether $y$ has a prime factor $p$ which is not a factor of $x$ - well then $p$ is not a factor of $h_1$, but will be a factor of $y_1$ where $y=y_1h_1$. Let $h_2$ be the highest common factor of $h_1$ and $y_1$ and $y_1=h_2y_2$. Then $y_2$ will retain any prime factor $p$ which is not a factor of $x$, and this will not be a factor of $h_2$. 
The $h_i$ are decreasing positive integers, so the process terminates. If some $h_i=1$ with $y_i\gt 1$ then $y$ has a prime factor which $x$ does not. Otherwise all the prime factors of $y$ must also be prime factors of $y$.

To illustrate with $x=168, y=132$ we have $h_1=12, y_1=11$ and $h_2=1, y_2=11$ detects a problem.
With $x=168, y=98$ we have $h_1=14, y_1=7$ and then $h_2=7, y_2=1$ and $h_3=1, y_3=1$ and all the prime factors of $y$ are factors of $x$.
Note the hcf can be determines by the Euclidean algorithm, without factoring $y$.
A: There's a pretty simple algorithm based on gcd.


*

*$c := \gcd(x,y)$. 

*$z := y / c$.

*If $z = 1$, terminate.  All prime factors in y were also in $x$.

*$c := \gcd(x,z)$.

*If $c = 1$, terminate.  $z > 1$ and $z$ divides $y$, but no prime factor of $z$ divides $x$.

*$z := z / c$.  

*Goto 3.  $z$ dimnishes every iteration, so we're guaranteed to terminate.

