Suppose $a,n \in \mathbb{Z}$, and $n>a>0$. How do I prove that $\nexists x \in \mathbb{Z}$ s.t. $nx = a$ ? I'm really not sure where to start on this one. I'd be happy if someone could give me a hint.

Edit: I've solved this by contradiction, but I will not be 'accepting' an answer from below because I did not use any one of them in a significant way to solve the problem.

  • $\begingroup$ That problem is just begging you to use proof by contradiction: assume that there is an integer such that nx = a. What happens to the relation? $\endgroup$ – user64878 Oct 7 '13 at 5:31
  • $\begingroup$ @MichaelGreinecker I believe the 'accepted answer' is meant to show to any other user which answer worked (best) for me to solve my problem. Since none of the answers below really helped me solve my problem and I did it by myself, I cannot say that any one answer was more useful than the rest in answering my question, so I cannot 'accept' an answer. $\endgroup$ – Newb Oct 7 '13 at 6:39

Assume there is such an $x$. Since $nx = a$, then $0 < nx$ and $nx < n$. Can you now prove that $0 < n$ and $n < 1$? And can you prove that that is a contradiction?

Edit: changed $p < q < r$ statements to $p < q$ and $q < r$ statements. Because hypothetically, I forgot what $<$ means.

Edit 2: Electric Boogaloo

So one way of defining $\mathbb{Z}$ is that it is a commutative ring with a subset $\mathbb{N}$ such that:

  1. Non-trivialty: $\mathbb{N} \ne \emptyset$.
  2. Closure: for all $a,b \in \mathbb{N}$, $ab \in \mathbb{N}$.
  3. Trichotomy: For all $x \in \mathbb{Z}$, exactly one of the following is true: $x \in \mathbb{N}$, $x = 0$, $-x \in \mathbb{N}$.
  4. Well-ordering principle: If $S \subseteq \mathbb{N}$ and is non-empty, there is an $x \in S$ such that for all $y \in S$, $x \le y$.

Now we can define $<$. We say $a < b$ if $b - a \in \mathbb{N}$.

So if you want to prove your statement from the ground up, you should prove:

  1. $a < b$ and $b < c \implies a < c$ (after this point you can write $a < b < c$)
  2. $ab > 0$ and $b > 0 \implies a > 0$ (useful for part 3)
  3. $ac < bc$ and $c > 0 \implies a < b$ (division not allowed)
  4. $0 < 1$, or equivalently $1 \in \mathbb{N}$ (master troll)
  5. $\not\exists x \in \mathbb{Z} \ 0 < x < 1$ (this one uses well-ordering)
  • 2
    $\begingroup$ This is a great point, most people don't realize that you need to prove there are no integers between $0$ and $1$. Also it isn't even clear that $0<1$, depending on your definition of $\mathbb Z$! $\endgroup$ – Dylan Yott Oct 7 '13 at 2:31
  • $\begingroup$ @DylanYott How does it depend on your definition of $\mathbb{Z}$? $\endgroup$ – Newb Oct 7 '13 at 2:32
  • $\begingroup$ You might define $0<1$ for example, but I don't think this is typical. $0<1$ follows from $\mathbb Z$ having a well-ordered subset $\mathbb N$ closed under both operations and satisfying trichotomy. Also you need $1 \in \mathbb N$. $\endgroup$ – Dylan Yott Oct 7 '13 at 2:36
  • $\begingroup$ @DylanYott I don't think that's necessary. $1>0$ follows from the order axioms and rules of arithmetic in $\mathbb{Z}$: if $a>0$ and $b>0$, then $ab>0$. Let $a=b=1$, then $1^{2} = 1 > 0$. $\endgroup$ – Newb Oct 7 '13 at 2:41
  • $\begingroup$ Let's do a thought experiment. I forgot what $>$ means. Could you define it for me? $\endgroup$ – Henry Swanson Oct 7 '13 at 2:56

Hint: Note that $|nx| = |n| |x|$, and consider the cases $x = 0$ and $|x| \ge1$ separately. Start by noting that $a < n$, so how are $|n| |x|$ and $a$ related?

  • $\begingroup$ Could you please elaborate a little? I'm also not sure if this is the cleanest approach to proving the proposition. $\endgroup$ – Newb Oct 7 '13 at 2:18
  • 2
    $\begingroup$ @Newb If $x = 0$, then $a = 0$ is a contradiction. If $x = \pm 1$, then $n = \pm x$, a contradiction. If $|x| > 1$, then $|nx| > n > a$. (Really, the last two cases don't even need to be handled separately.) $\endgroup$ – user61527 Oct 7 '13 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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