I need help solving the following. My idea is to use Euclid's algorithm however I was told that I can simply prove this just with natural numbers.

Prove that for all natural numbers $c$ and $d$, if $c|d$ then $c ≤ d.$


closed as off-topic by user21820, Xander Henderson, José Carlos Santos, Saad, Parcly Taxel Mar 26 at 3:27

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, Xander Henderson, José Carlos Santos, Saad, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ If $n\in\Bbb N$ then $n\ge1$. $\endgroup$ – Lord Shark the Unknown Mar 7 at 6:31
  • 1
    $\begingroup$ What does $c\mid d$ mean to you? $\endgroup$ – Arthur Mar 7 at 6:32
  • 2
    $\begingroup$ And what does that mean? $\endgroup$ – Arthur Mar 7 at 6:37
  • 2
    $\begingroup$ That's not the definition of the word "divides". What does the phrase "$c$ divides $d$" actually mean? $\endgroup$ – Arthur Mar 7 at 6:42
  • 1
    $\begingroup$ What Arthur is trying to get at, @k.rudin, is the actual definition of what it means for a number to divide another. What is the exact relation between them? There's an equation somewhat associated with this, depending on how it was introduced to you. $\endgroup$ – Eevee Trainer Mar 7 at 6:46

Hint: (broad overview)

Recall what it means for a natural number to divide another - it means one is an integer multiple of the other. Since both are positive, that integer must also be positive (i.e. it is $1$ or $2$ or $3$ or ...).

Consider the ratio of the first two integers and see what you can conclude.


If $c,d \in \Bbb N$ with $c|d$, then there exists $n \in \Bbb Z^+$ such that

$$d = nc$$

Consider the ratio of $d$ and $c$:

$$\frac d c = n$$

Since $n$ is a positive integer,

$$\frac d c = n \geq 1 \implies \frac d c \geq 1 \implies d \geq c$$

concluding the proof.


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