Wednesday, October 31, 2018

number theory - If $a mid m$ and $(a + 1) mid m$, prove $a(a + 1) | m$.



Can anyone help me out here? Can't seem to find the right rules of divisibility to show this:




If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.


Answer



It is not surprising that you are finding this difficult, because it goes beyond basic divisibility rules -- it rather requires something which is essentially equivalent to the uniqueness of prime factorization. [Edit: Actually this is comment is incorrect -- as Robin Chapman's answer shows, it is possible to prove this using just divisibility rules. In particular it is true in any integral domain.]



I assume $a$ and $m$ are positive integers. The first observation is that $a$ and $a+1$ are relatively prime: i.e., there is no integer $d > 1$ -- or equivalently, no prime number-- which divides both $a$ and $a+1$, for then $d$ would have to divide $(a+1) - a = 1$, so $d = 1$.



Now the key step: since $a$ divides $m$, we may write $m = aM$ for some positive integer $M$. So $a+1$ divides $aM$ and is relatively prime to $a$. I claim that this implies $a+1$ divides $M$. Assuming this, we have $M = (a+1)N$, say, so altogether



$m = aM = a(a+1)N$, so $a(a+1)$ divides $m$.




The claim is a special case of:



(Generalized) Euclid's Lemma: Let $a,b,c$ be positive integers. Suppose $a$ divides $bc$ and $a$ is relatively prime to $b$. Then $a$ divides $c$.



A formal proof of this requires some work! See for instance



http://en.wikipedia.org/wiki/Euclid's_lemma



In particular, proving this is essentialy as hard as proving the fundamental theorem of arithmetic.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...