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<c

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<r<c.

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

Advertisements

15 Comments

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<r

0\le (a-bt)-b<r

if

0<a-b(t+1)<r

this contradicts the choice for   r

then

0\le r<b

Now for uniqueness:

suppose

a=bt+r,\qquad 0\le r<b

and

a=bt'+r',\qquad 0\le r'<b

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

Leave a comment

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!

Follow the soap opera:

 

 

 

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

or

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

2 Comments

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)

2 Comments

Filed under math