# Simple divisibility proof

Given integers $a$, $k$, and $n$, and given that $a(a+1)=n(2^k)$, how do I prove that (assuming $a$ is even), $2^k|a$?

I read this in a proof, and I can't figure out how to verify it myself.

-
$a(a+1)=a^2+a$. – Holdsworth88 Jan 23 '12 at 2:40

If $a$ is even, then $a+1$ is odd which is not divisible by $2$. Therefore, if $a(a+1)=n(2^k)$, i.e. if $a(a+1)$ is divisible by $2^k$, we must have $a$ us divisible by $2^k$, since $a+1$ is not divisible by $2$.

For example, take $a=24$, then $a+1=25$ and $a(a+1)=75(2^3)$. Since $a+1=25$ is odd, it is not divisible by $2$. Therefore, $2^3$ must divide $a=24$.

-
Alas, this argument is either incorrect, incomplete, or circular. It would help to elaborate so it is clear what you intend. – Bill Dubuque Jan 23 '12 at 3:22
Don't you see the gap? Hint: does your argument work for the slightly more general case in my answer where $\rm\ 2\to c\:.$ It's still not clear to me precisely what you propose as proof since you leave too much unsaid. Precision is crucial, especially at this level. Without such, there's no way to distinguish a correct proof (missing details) from one that is incorrect, circular, etc. – Bill Dubuque Jan 23 '12 at 3:59
You claim that because $a+1$ is not divisible by $2$, if $a(a+1)$ is divisible by $2^k$, then $a$ is divisible by $2^k$. Let me rephrase in such a way that I don't change any of what you have claimed. Because $b$ is not divisible by $6$, if $ab$ is divisible by $6^k$, then $a$ is divisible by $6^k$. However, let $a=9$ and $b=4$. $b$ is not divisible by $6$, and $ab$ is divisible by $6^2$, your argument would conclude that $9$ is divisible by $6^2$. In what way is $2$ different than $6$? – robjohn Jan 24 '12 at 0:47
My guess (but perhaps I have misinterpreted him) is that Bill's point is that your proof implicitly uses the fact that $2$ is prime and hides an inductive step. It is not that there is a mistake per se in your proof, but that the same formal argument does not quite work in similar settings, showing that there are hidden assumptions. (It comes down, as said in Bill's answer below, to a use of the Euclidean algorithm to prove these "obvious" facts about factorization of integers) – user16299 Jan 24 '12 at 0:51
I find Bill Dubuque's first comment on this answer useful and insightful. – user23211 Jan 24 '12 at 1:03

Consider the prime factorization of $a + 1$. Since $a$ is even, $a + 1$ is not. Now consider the prime factorization of $a(a + 1)$: $2^k$ must appear somewhere, and no 2 is contributed by the factorization of $a + 1$, so that $2^k$ must appear in the prime factorization of $a$.

-
This question is of such an elementary nature, the Fundamental Theorem of Arithmetic seems like overkill. – robjohn Jan 24 '12 at 1:53
@robjohn: Maybe so, but it's such a convenient tool. Sure, you could light a fire by rubbing two sticks together, but why bother (except to learn how it's done) when you can use a lighter? – Ilmari Karonen Feb 11 '12 at 0:22
If, when proving very elementary results, one uses a result that is far more advanced, there is a great risk of getting caught in a circular argument, where the simple result is, in some part, used to prove the more advanced one. – robjohn Feb 11 '12 at 0:40
@robjohn: Your point would hold if this question came up in a deductive text in elementary number theory. However it seems extremely unlikely that this question would serve at any point in a proof of the Fundamental Theorem of Arithmetic. – Marc van Leeuwen Dec 26 '12 at 7:03

Hint $\: \$ If $\rm\:\ \color{#C00}{c\ |\ a}\ \:$ then $\rm\:\ \color{#0A0}{c\ |\ b\ (a+1)}\ \,\Rightarrow\,\ c\ |\ b\ \$ since $\rm\: \ \dfrac{b}c\, =\, \color{#0A0}{\dfrac{b\ (a+1)}c} -\ b\ \color{#C00}{\dfrac{a}c}\, \in\, \mathbb Z\! -\! b\,\Bbb Z\,\subset\, \Bbb Z$

Hence, by induction, $\rm\ \ c^k\ |\ b\ (a+1)\ \Rightarrow\ c^k\ |\ b\:.\$ Yours is the special case $\rm\ c = 2,\ \: b = a$

Remark $\$ More generally $\rm\ c^k\ |\ b\ d\ \ \Rightarrow\ \ c^k\ |\ b\ \:$ if $\rm\:\ gcd(c,d) = 1\ \$ by Euclid's Lemma.

-
I don't understand the downvotes. The hint is excellent and would be a proof if the induction were spelled out. Anyone care to explain? – robjohn Jan 24 '12 at 15:54
I don't understand the hints, but colors the bright colors are excellent so +1. ;) – David H Jul 10 '13 at 10:54

Let $a=2^x*b$ with $b$ odd and $x \ge 1$, and let $y = x - k$. Now the equation can be written as $n = 2^y*b*(a+1)$. Because both $b$ and $a+1$ are odd and $n$ is an integer, $y \ge 0$. But then $a = 2^x*b = 2^k*2^y*b$ and therefore $2^k \vert a$.

-