Find all natural numbers $d$ which make the following statement true:

"For all integers $w, x, y, z,$ if $w\mid{x}$, $y\mid{z}$ and gcd($x,z$)=$d$, then gcd($w,y$)=$d$."

It says that we must justify our answer with a proof, and show that these values of $d$ would result in a true statement, and all other values of $d$ would be false.

I'm not sure how to approach this question; any help would be appreciated, thanks!


closed as off-topic by user21820, Song, José Carlos Santos, Alex Provost, jgon Mar 12 at 21:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Song, José Carlos Santos, Alex Provost, jgon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Have you tried some numerical examples? Take lots of small (single-digit) values of $x,z$, then the possible values of $w,y$, and calculate the gcds and see when the statement is true. $\endgroup$ – Greg Martin Feb 26 at 4:32
  • $\begingroup$ I have, but I don't see any pattern yet and I'm not sure how to prove it. $\endgroup$ – macy Feb 26 at 4:35
  • $\begingroup$ Perhaps list (in the problem statement) some examples you found where the two gcds were equal, and list some example where they were not equal. Maybe we can help you spot the pattern.... $\endgroup$ – Greg Martin Feb 26 at 4:36
  • 1
    $\begingroup$ There's nothing stopping $w$ from being $1$, is there? And if it is, what are the consequences? $\endgroup$ – Gerry Myerson Feb 26 at 5:25


Assume it is true for $d $.

Let $w,z$ be relatively prime. Let $x=wd $ and let $y=zd $.

What is $\gcd (x,y) $? What is $\gcd (w,z) $?

Bear in mind that 1) $w,z $ are relatively prime and 2) if $\gcd (x,y)=d $ then $\gcd (w,z)=d $.


For example. Let $w=2;z=3;x=2d;y=3d $. What happens?


The equality fails in general, e.g. $(w,y)=(1,1)\neq (x,x)=(x,z)\ $ if $\,x>1$
But divisibility is true and often useful, i.e.

Lemma $\ \ \begin{align} w\mid x\\ y\mid z\,\end{align}\,\Rightarrow\ (w,y)\mid (x,z)$

Proof $\ \ \begin{align}&(w,y)\mid w\mid x\\ &(w,y)\mid y\,\mid z\end{align}\Rightarrow\,(w,y)\mid (x,z)$


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