Proof ax + bx = 1
wessie
I would like to know if my proof is unique. It does not use the Euclidean
Algorithm.
Any comments on my proof are welcome.
Prove that an a and b can be found such that ax + bx =1 given (x,y) = 1 and
all variables integers.
Now if (x,y) = 1 then y = x r_ 1 + r_2 equation 1
Note r_2 < x (the remainder is smaller than the divider)
Also note that the divider and divided has no common factors and hence the
remainder has no common factors with the divider or the divided.
Doing the process again using the remainder as the new divider
y = r_2 r_3 + r_4 and again we see that r_4 < r_2 equation 2
repeat the process again
y = r_4 r_5 + r_6 and we have r_6 < r_4 equation 3
repeat the process again and again until the remainder is one.
y = r_n r_m + 1
Note the remainder will become smaller each time and this will happen
because the remainder is always smaller than the divider. Each new division
we use the previous remainder as divider and thus the remainder shrinks. The
end remainder will be one and this is because the divider each time has no
common factors with the divided.(y,x)=(y , r_2) = (y ,r_n) = 1
There will therefore be a remainder with each division that shrinks until
unity. Now we back substitute.
We do this as follows:
Equation 2 into equation 1 which becomes equation s
Equation 3 into equation s which becomes equation s+1
Equation 4 into equation s+1 which becomes s+2
and so on until the last equation has been substituted.
Lets follow this logic.
We multiply equation one with r_3 and add r_4
y r_3 + r_4 = (x r_ 1 + r_2) r_3 + r_4 = x t + r_2 r_3 + r_4 = xt + y
So y(r_3 - 1) + r_4 = xt
so sy + r_4 = xt
Again substitute (sy + r_4) r_5 + r_6 = xt r_5 + r_6
So sy + y = xg + r_6
So ky = gx + r_6
We repeat this process up until the last equation and we have vy + wx = 1
So w=b and v=a and we have ax+by=1
Example
Let y = 19 and x = 5
Then 19 = 5.3 + 4
19 = 4.4 + 3
19 = 3.6 + 1
So 19.4 + 3 = 5.3.4 + 4.4 +3 = 5.12 + 19
So 19.3 + 3 = 5.12
So 19.3.6 + 3.6 + 1 = 5.12 .6 + 1
So 19.18 + 19 = 5.72 + 1
So 19.19 - 5.72 = 1
So b= 19 and a = -72
Carel
Author of "Paradox" , a book on brain teasers
Have a look at http://www.1stbooks.com/bookview/9687
Robin Chapman
> Dear group
>
> I would like to know if my proof is unique.
I'm sure it's unique, but is it a proof?
> It does not use the Euclidean
> Algorithm.
>
> Any comments on my proof are welcome.
>
> Prove that an a and b can be found such that ax + bx =1 given (x,y) = 1 and
> all variables integers.
ax + by = 1 surely.
Let's take x = 5 and y = 12. Certainly (5,12) = 1.
> Now if (x,y) = 1 then y = x r_ 1 + r_2 equation 1
>
> Note r_2 < x (the remainder is smaller than the divider)
Aha! 12 = 5 . 2 + 2 so r_1 = r_2 = 2.
> Also note that the divider and divided has no common factors and hence the
> remainder has no common factors with the divider or the divided.
Now what are the "divider" and "divided"? The remainder 2 here has
no common factor with x, but it does have one with y.
> Doing the process again using the remainder as the new divider
>
> y = r_2 r_3 + r_4 and again we see that r_4 < r_2 equation 2
So 12 = 2 . 6 + 0 so r_4 = 0 ....
> repeat the process again
>
> y = r_4 r_5 + r_6 and we have r_6 < r_4 equation 3
>
> repeat the process again and again until the remainder is one.
I don't think we'll ever reach that stage :-(
OK your argument will work if y is a prime; however as we have
seen, if y is composite, it may break down.
Robin Chapman
Arturo Magidin
>I would like to know if my proof is unique.
What is it that makes a proof unique?
> It does not use the Euclidean Algorithm.
It ->IS<- the Euclidean Algorithm. What are you talking about?
(Easy exercise: modify your argument to show that if the gcd of a and
b is d, then repeated division with remainder will produce integers x
and y such that ax+by = d.)
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Arturo Magidin
>I would like to know if my proof is unique. It does not use the Euclidean
>Algorithm.
It's been pointed out to me that I was too hasty in going over this
and I missed the mistakes therein...
>Any comments on my proof are welcome.
>
>Prove that an a and b can be found such that ax + bx =1 given (x,y) = 1 and
>all variables integers.
>
>Now if (x,y) = 1 then y = x r_ 1 + r_2 equation 1
>
>Note r_2 < x (the remainder is smaller than the divider)
Though not much in use, in this situation x is called "divisor"; y is
called "dividend".
>Also note that the divider and divided has no common factors and hence the
>remainder has no common factors with the divider or the divided.
And this is wrong; the remainder certainly has no (nontrivial) common
factors with the divisor, since any common factor of x and r_2 is a
common divisor of y; but any common divisor of r_2 and y (the
remainder and the dividend) is a divisor of x*r_1, and it could easily
be a divisor of r_1 rather than x, so there is no justification for
the claim that the remainder has no common factors with the dividend.
>Doing the process again using the remainder as the new divider
>
>y = r_2 r_3 + r_4 and again we see that r_4 < r_2 equation 2
>
>repeat the process again
>
>y = r_4 r_5 + r_6 and we have r_6 < r_4 equation 3
>
>repeat the process again and again until the remainder is one.
Though you can repeat the process until the remainder is 0, you cannot
guarantee that the previous step the divisor was 1; you are claiming
that:
"If (x,y) = 1, and y=xq+r, then (y,r)=1"
and this is false in general. E.g. if y<x, then q=0 and r=y, so unless
y=1 to begin with... But other examples abound.
Arturo Magidin
Since there was no assumption that y>x, the argument may break down
even if y is prime: take y=3 and x=5; you get r_1=0 and r_2=y=3. Of
course, that little problem is fixed if we further assume not only
that y is prime, but also that y>x.
wessie
So by changing my proof by stating x,y must be prime the proof becomes valid
"Robin Chapman" <r...@maths.ex.ac.uk> wrote in message
news:a31ba6bf.02120...@posting.google.com...
> "wessie" <wess...@hotmail.com> wrote in message
news:<3df02...@news1.mweb.co.za>...
> > Dear group
> >
> > I would like to know if my proof is unique.
>
> I'm sure it's unique, but is it a proof?
>
> > It does not use the Euclidean
> > Algorithm.
> >
> > Any comments on my proof are welcome.
> >
> > Prove that an a and b can be found such that ax + bx =1 given (x,y) = 1
and *this added now x,y prime
Arturo Magidin
>Thanks Robin
>
>So by changing my proof by stating x,y must be prime the proof becomes valid
No. You must also specify that y>x; otherwise, you get r_1=0 and
r_2=y, and you still don't get the result you want.
Bill Dubuque
>wessie <wess...@hotmail.com> wrote: (forked from thread [1])
>>
>> Any comments on my proof are welcome
>
> as we have seen, if y is composite, it may break down.
This special case of the Euclidean algorithm computes inverses
mod p prime [it is essentially Gauss: Disq. Arith. Art.5, 1801],
iterating (a,p) -> (p mod a, p) i.e. a->a'->a''.., x' = p mod x
instead of (a,p) -> (p mod a, a) as in the Euclidean algorithm.
It generates a descending chain of multiples of a (mod p), e.g.
mod 103: 60's inverse is computed as follows
103 = 60*1 + 43 = 43*2 + 17 = 17*6 + 1, graphing the descent:
* -1 * -2 * -6 => 60(-1)(-2)(-6) = 1 (mod 103)
mod 103: 60 -----> 43 -----> 17 -----> 1 checking: -720 = 1 - 7 (103)
* 2 * -6
Quicker: 60 -----> 17 -----> 1 by allowing +/- multipliers/remainders.
Note the multiples are all nonzero: p mod a != 0, i.e. not a|p since
p being prime has no proper divisor a with 1 < |a| < p. The multiples
descend in magnitude: |a| > |p mod a|, hence they eventually reach +-1.
What Gauss proved was slightly different, but essentially equivalent.
He employed the same descent (p,a) => (p, p mod a) to instead prove
EUCLID'S LEMMA: p|ba => p|b or p|a, via p|ba => p|b(p mod a) = b(p-qa).
In effect, this yields b = 0 from ba = 0 by multiplying through
by 1/a (mod p), where the inverse is computed in stages just as above.
This leads Gauss to the first known proof of the fundamental theorem
of arithmetic: every positive integer has a unique factorization
into primes. Apparently Gauss was the first ever to notice that this
required proof. Before Gauss it seems uniqueness was taken for granted,
sometimes deemed a "law of thought", even by 20'th century textbooks!
[cf. Davenport: Higher Arithmetic]. Surprisingly, this is the extent
of the Euclidean algorithm in Disq. Arith. Indeed, as John Stillwell
writes in his delightful introductory textbook: Numbers and Geometry:
Gauss avoided use or mention of the Euclidean algorithm in his
Disquisitiones Arithmeticae. He avoided using it for the fundamental
theorem of arithmetic by giving a direct proof, by descent, of the
prime divisor property [Euclid's lemma above -wgd]. He did not even
mention it when discussing the gcd and lcm, giving instead the rules
for computing them from prime factorizations and saying only that
we know from elementary considerations how to solve these problems
when the resolution of the numbers A, B, C into factors are not
given (Disq. Arith., article 18)
And he hid its role in the solution of ax + by = 1 (article 28)
by referring only to the so-called "continued fraction" method,
which is equivalent.
Dirichlet simplified, and in some ways extended, the Disquisitiones
in his Vorlesungen uber Zahlentheorie (lectures on number theory) of
1867. One of his reforms was reinstatement of the Euclidean algorithm.
He used it to derive the fundamental theorem and related results much
as we have in this chapter, and went so far to say
It is now clear that the whole structure rests on a *single*
foundation, namely the algorithm for finding the greatest common
divisor of two numbers. All the subsequent theorems, even when they
depend on the later concepts of relative and absolute prime numbers,
are still only simple consequences of the result of this initial
investigation ... (Dirichlet (1867), S.16)
One of the reasons Dirichlet was enthusiastic about the Euclidean
algorithm was that it could be used in other situations, a fact
that also converted Gauss in the end. In 1831, Gauss found it useful
to introduce what are now called Gaussian integers - numbers of the
form a + b sqrt(-1), which we shall study in Chapter 7 - and found
that the key to their arithmetic was the applicability of the Euclid-
ean algorithm. Perhaps it was with this generalization in mind that
Dirichlet based his number theory on the Euclidean algorithm from
the beginning, because the passage quoted above continues:
... so one is entitled to make the following claim: any analogous
theory, for which their is a similar algorithm for the greatest
common divisor, must also have consequences analogous to those
in our theory.
[John Stillwell: Numbers and Geometry, p.22, Springer, UTM, 1998]
Dirichlet's insight was right on the money: the structural foundations
underlying this approach to unique factorization are now abstracted
in the theory of Euclidean domains - those domains which, like the
integers and Gaussian integers, possess a Division Algorithm. This
simple pretty theory can be found in most abstract algebra textbooks,
e.g. Herstein (Topics), Hungerford, Jacobson, or Zariski and Samuel.
Returning to the modular inversion algorithm, compare it with the
inversion algorithm obtained via the Chinese Remainder Theorem [2]
x (1/x mod y) + y (1/y mod x) = 1 (mod xy)
=> 1/x mod y = (1 - y (1/y mod x))/x
e.g. 1/60 mod 103 = (1 - 103 (1/103 mod 60))/60 = -12, via inverse below
1/103 = -1/17 mod 60 = (1 - 60 (1/60 mod 17))/17 = 7, via inverse below
1/60 = 1/9 mod 17 = (1 - 17 (1/17 mod 9))/9 = 2, now subst. above
-Bill Dubuque
[1] Here's the original thread by carel: ax + by = 1, 2002-11-29
http://groups.google.com/groups?threadm=3de75e13.0%40news1.mweb.co.za
[2] Modular inversion via the Chinese Remainder Theorem
http://groups.google.com/groups?threadm=y8z65xti7pn.fsf%40nestle.ai.mit.edu
Helmut Richter
> What is it that makes a proof unique?
>
>> It does not use the Euclidean Algorithm.
>
> It ->IS<- the Euclidean Algorithm. What are you talking about?
>
> (Easy exercise: modify your argument to show that if the gcd of a and
> b is d, then repeated division with remainder will produce integers x
> and y such that ax+by = d.)
I have not followed the details in this particular thread, but it is
certainly so that "ax+by=gcd(a,b)" can be proved with a *single*
integer division with remainder - in contrast to the Euclidean
Algorithm which is based on a *repeated* integer division. Not using
the Euclidean Algorithm is thus possible.
Helmut Richter
Arturo Magidin
Yes. I mistakenly thought that the argument the Other Poster had
presented was in fact the Euclidean Algorithm; she divided x by y,
then took the remainder, but instead of dividing y by the remainder,
the OP again divided x by the remainder. I did not realize this was
happening, so I thought it was just the Euclidean Algorithm. In fact,
her argument was flawed.
Arturo Magidin, sans sig.