1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove a|1 iff a = ±1

  1. Jan 6, 2013 #1
    Hi, can I get someone to look over this proof? I'm okay with the first part, but can I get some reassurance or feedback on the second part? Namely, am I right about what I'm intending to show? Thanks.

    1. The problem statement, all variables and given/known data
    The following statement holds for all [itex]a,b,c,d \in \mathbb{Z}:[/itex]
    [itex]a | 1\mbox{ iff } a=\pm 1[/itex]

    Write a proof for this part of Theorem 2.3.6 (which just lists other properties I've written proofs for).

    2. Relevant equations

    3. The attempt at a solution

    First I wrote a proof for the left-to-right conditional:
    Assume [itex]a|1[/itex]. Then, by definition, [itex]\exists k\in\mathbb{Z}[/itex] such that [itex]ak = 1[/itex].

    Suppose [itex]k>1[/itex]. Then [itex]ak = 1 \Rightarrow a = \frac{1}{k} \not\in\mathbb{Z}[/itex].
    Suppose [itex]k=1[/itex]. Then [itex]ak = 1 \Rightarrow a = 1[/itex].
    Suppose [itex]-1 < k < 1[/itex]. Then [itex]k = 0[/itex], but [itex]0a \not=1[/itex] for any [itex]a[/itex].
    Suppose [itex]k=-1[/itex]. Then [itex]ak = 1 \Rightarrow a = -1[/itex].
    Suppose [itex]k<-1[/itex]. Then [itex]ak = 1 \Rightarrow a = -\frac{1}{k} \not\in\mathbb{Z}[/itex].

    The first, third, and fifth scenarios all lead to contradictions. In the remaining cases, [itex]a=\pm1[/itex].

    (I had a feeling my approach here was a bit tedious, but if it's acceptable, I'm fine with it.)

    Assume [itex]a=\pm1[/itex]. To show that [itex]a|1[/itex], suppose that [itex]ak=1[/itex] for some [itex]k[/itex]. If [itex]k \in\mathbb{Z}[/itex], then both [itex]k|1[/itex] and [itex]a|1[/itex], the latter of which I want to show.

    Case 1: Let [itex]a=1[/itex]. Then we have [itex](1)k = 1 \Rightarrow k = 1 \in\mathbb{Z}[/itex].
    Case 2: Let [itex]a=-1[/itex]. Then we have [itex](-1)k = 1 \Rightarrow k=-1 \in\mathbb{Z}[/itex].

    Since both cases imply that [itex]k \in\mathbb{Z}[/itex], I conclude that [itex]a|1[/itex].
  2. jcsd
  3. Jan 6, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    You could reduce this to the cases k=0, |k|=1, |k|>1, but I think the idea is fine.

    You can prove "<=" like that, but you can simply give some specific k, you don't have to derive that there is no other value.
  4. Jan 8, 2013 #3
    You use the fact that ##k\not\in\{1,-1\}\Rightarrow \frac{1}{k}\not\in\mathbb{Z}##, when that is essentially what you're trying to prove for ##a##. Actually that's the contrapositive of what you're trying to prove; ##\frac{1}{a}\in\mathbb{Z}\Rightarrow a\in\{1,-1\}##. So that's bad.

    Actually, you're working in ##\mathbb{Z}##, so what does ##\frac{1}{k}## even mean? If you are learning this stuff the way that I learned it, all of the statements about division for integers have been expressed in terms of multiplication. So it's probably a good idea to restrict yourself to using only facts about multiplication. It's OK to use what you know from other classes to gain insight into the problem or figure out how the solutions should go, but that doesn't mean you're free to use that information in the proof.

    For instance, you know that the rational reciprocals of integers larger than 1 must be between 0 and 1. How do you go about saying that without referencing rationals or reciprocals? Can you get away with saying something slightly different (perhaps like ##nm>m## if ##n,m>1##*) that only uses facts about integers and integer multiplication? That's the problem that you're being asked to do here.

    *You should be able to prove this from the definitions of multiplication for natural numbers and the definition of < for natural numbers if you've seen these definitions.
  5. Jan 9, 2013 #4


    User Avatar
    2017 Award

    Staff: Mentor

    You can use multiplication and division in the real numbers, and see that the solutions are not integers afterwards. As operations with integers give the same result as operations with the corresponding real numbers, this works.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook