# Tag Archives: number theory

## the greatest common divisor exists!

for the sake of all of us, let us assert and demonstrate:

$\forall a,b\in{\mathbb{Z}}$ the $GCD(a,b)$ exists and its is unique

Proof:

Consider the auxiliar set $T_{ab}=\{am+bn>0\ :\ m,n\in{\mathbb{Z}}\}$

as a piece of ${\mathbb{N}}$ there exists $c=\min\ T_{ab}$.

But if $c\in T_{ab}$ then $c=a\mu+b\nu$ for some $\mu,\nu\in{\mathbb{Z}}$.

We are going to check that $c$ satisfy the $GCD$ for $a,b$:

Claim: $c|a$

Applying the divisions’ algorithm to this  pair we get

$a=ct+r$ with $0\le r

Since $r=a-ct=a-(a\mu+b\nu)t=a(1-\mu t)+b(-\nu t)\ge0$

If $r>0$ then $r\in T_{ab}$ and $0.

This contradicts the choice for $c$, then $r=0$ and the claim follows.

Similarly $c|b$.

So $c$ is a common divisor of $a,b$.

Uniqueness:

Now suppose that $d$ is a positive integer that $d|a$, $d|b$ and for any other $l$ which divides $a,b$ implies $l|d$.

Then, since $c$ divides both $a,b$ then $c|d$.

Additionally $d|a,\ d|b$ implies $d|a\mu,\ d|b\nu$ and $d|(a\mu+b\nu)$, hence $d|c$

Then $c|d$ and $d|c$. That is $d=\pm c$, but $d=c$ is the only possible.

$\Box$

Filed under cucei math, group theory, numbers

## division’s algorithm

let us write for the sake of young mathematicians this important arithmetic fact:

PROPOSITION:

$\forall a,b\in{\Bbb{Z}}\ \exists t,r\in{\Bbb{Z}}\ : a=bt+r,\quad 0\le r<|b|$

PROOF:

Let $a>b>0$ be the case and we set

$S_{ab}=\{a-bm\ge0\ |\ m\in{\Bbb{Z}}\}$

then there exists

$\exists$ $r=\min S_{ab}$.

If

$r=0$

then

$a=bt$.

For the rest of the argument we consider

$r>0$.

So

$r=a-bt,\qquad \exists t\in{\Bbb{Z}}$

and $a=bt+r$.

We are going to establish

$0\le r< b$.

Suppose

$r\ge b$

$r-b\ge0$

$0\le r-b

$0\le (a-bt)-b

if

$0

this contradicts the choice for   $r$

then

$0\le r

Now for uniqueness:

suppose

$a=bt+r,\qquad 0\le r

and

$a=bt'+r',\qquad 0\le r'

$r\ge r'$

$r-r'\ge 0$

but

$b(t'-t)=r-r'$ and

$b(t-t')=-r'+r>-r>-b$

are  integer multiples of $b$ between

$-b$ and $b$

then

$b(t-t')=0$

and

$t'-t=0$

since $b\neq0$.

So $t=t'$ and $r=r'$

$\Box$

Filed under math

## allocated quizz on the MO

$\sum_{k=0}^{n}\frac{4^k(k+1)}{{2k\choose k}}=\frac{4^{n+1}(2n^2+5n+2)}{5{2(n+1)\choose n+1}}+\frac{1}{5}$

found!

http://mathoverflow.net/questions/67784/finite-sum-of-integers-inverses

or

http://mathoverflow.net/questions/68090/finite-sums-with-binomial-and-catalan-inverses

Filed under math

## 3, 7, 15, 23, 39, 47, 71, 87, 111, 127, …

10 Siehler’s numbers

two consecutive reciprocal partial sums are

$1/3+1/7+1/15+1/23+1/39+1/47+1/71+1/87+1/111+1/127+1/167+1/183+1/231+1/255+1/287+1/319+1/383+1/407+1/479+1/511+1/559+1/599+1/687+1/719+1/799+1/847+1/919+1/967+1/10794$

$\approx 0.722936$

and

$1/3+1/7+1/15+1/23+1/39+1/47+1/71+1/87+1/111+1/127+1/167+1/183+1/231+1/255+1/287+1/319+1/383+1/407+1/479+1/511+1/559+1/599+1/687+1/719+1/799+1/847+1/919+1/967+1/1079+$

$1/1111 \approx 0.723836$

(04.nov.2011)

by the way: $f(n)=\#{\mathbb{Z}_n}^*$ (cardinal of multiplicatively invertibles elements in the ring ${\mathbb{Z}_n}$) satisfy:

• $f(1)=\#{\mathbb{Z}_1}^*=0$, since ${\mathbb{Z}_1}=\{0\}$ and ${\mathbb{Z}_1}^*=\varnothing$
• $f(2)=\#{\mathbb{Z}_2}^*=1$, since ${\mathbb{Z}_2}=\{0,1\}$ and ${\mathbb{Z}_2}^*=\{1\}$
• $f(3)=\#{\mathbb{Z}_3}^*=2$, since ${\mathbb{Z}_3}=\{0,1,2\}$ and ${\mathbb{Z}_3}^*=\{1,2\}$
• $f(4)=\#{\mathbb{Z}_4}^*=2$, since ${\mathbb{Z}_4}=\{0,1,2,3\}$ and ${\mathbb{Z}_4}^*=\{1,3\}$
• $f(5)=\#{\mathbb{Z}_4}^*=4$, since ${\mathbb{Z}_5}=\{0,1,2,3,4\}$ and ${\mathbb{Z}_4}^*=\{1,2,3,4\}$

Hence

$s(1)=3+4f(1)=3$

$s(2)=s(1)+4f(2)=7$

$s(3)=s(2)+4f(3)=15$

$s(4)=s(3)+4f(4)=23$

$s(5)=s(4)+4f(5)=39$

$s(n+1)=s(n)+4f(n+1)$