Greatest Common Factor
William Elliot
(a,b)^n = (a^n, b^n).
Is that correct? If so, how does one prove it?
-- For your entertainment.
If n in N, q in Q and q^n in N, then q in Z.
Hints, even proof if needed, upon request.
----
Pubkeybreaker
Write the GCD in terms of the prime factorizations of a & b.
William Elliot
> On Nov 14, 7:32 am, William Elliot <ma...@rdrop.remove.com> wrote:
>> Apparently if a,b,n in N, then
>> . . (a,b)^n = (a^n, b^n).
>>
>> Is that correct? If so, how does one prove it?
>>
> Write the GCD in terms of the prime factorizations of a & b.
>
I presume that's in reply to the above problem and not the problem
that I clipped. Ok, just use
. . n.min{ r,s } = min{ nr,ns }
Is there a way to proof this without prime factorization?
JEMebius
Yes, indeed GCD(a^n, b^n) = (GCD(a, b))^n.
PROOF: With help of the theorem on decomposition into prime factors.
A and B have unique decompositions into prime factors:
A = PROD of Pi^Ni for i=1 to number of distinct prime factors Pi; likewise B.
If one allows exponents equal to zero then one can put
A = PROD of Pi^Ki over all primes Pi whatsoever with only a finite number of exponents Ki > 0;
B = PROD of Pi^Li over all primes Pi whatsoever with only a finite number of exponents Li > 0.
Then GCD(A, B) = PROD of Pi^[min (Ki, Li)], and
GCD (A^n, B^n) =
PROD of Pi^[min (n*Ki, n*Li)] =
PROD of Pi^[n * min (Ki, Li)] =
GCD (A, B)^n
Done.
By the way, LCM(A, B) = PROD of Pi^[max (Ki, Li)]; min(A, B) + max(A, B) = A + B;
hence GCD(A, B) * LCM(A, B) = A * B.
Ciao: Johan E. Mebius
JEMebius
I do not know, but you could try the subject of Abelian Semigroups:
http://en.wikipedia.org/wiki/Abelian_semigroup#Special_classes_of_semigroups
or http://en.wikipedia.org/wiki/Greatest_common_divisor for just the subject of GCD.
Good luck: Johan E. Mebius
Dan Cass
To prove (a, b)^n = (a^n, b^n),
without prime factorization,
use the following fact:
[*] For positive integers u,v we have (u,v) = k
iff there are positive coprime integers u' and v'
with u = k u' and v = k v'.
Suppose (a,b) = d and write a = d a' and b = d b' with (a' ,b') = 1.
Then a^n = d^n * a' ^ n and b^n = d^n * b' ^ n.
Since (a', b') = 1 one has also (a' ^ n, b' ^ n) = 1.
Therefore using [*] we get (a^n, b^n) = d^n.
Michael Stemper
>-- For your entertainment.
>
>If n in N, q in Q and q^n in N, then q in Z.
I came up with a proof of this a few years back. My proof only discussed
n=2, but would be equally valid for any n in N+. (Note that the theorem
is false for n=0).
I found this a much more appealing proof of the irrationality of
sqrt(2) than the classic one.
--
Michael F. Stemper
#include <Standard_Disclaimer>
Nostalgia just ain't what it used to be.
rio
"Dan Cass" <dc...@sjfc.edu> ha scritto nel messaggio
news:33068335.1226675375...@nitrogen.mathforum.org...
>> On Fri, 14 Nov 2008, Pubkeybreaker wrote:
>> > On Nov 14, 7:32 am, William Elliot
>> <ma...@rdrop.remove.com> wrote:
>>
>> >> Apparently if a,b,n in N, then
>> >> . . (a,b)^n = (a^n, b^n).
>> >>
>> >> Is that correct? If so, how does one prove it?
>> >>
>> > Write the GCD in terms of the prime factorizations
>> of a & b.
>> >
>> I presume that's in reply to the above problem and
>> not the problem
>> that I clipped. Ok, just use
>> . . n.min{ r,s } = min{ nr,ns }
>>
>> Is there a way to proof this without prime
>> factorization?
>
> To prove (a, b)^n = (a^n, b^n),
> without prime factorization,
> use the following fact:
>
> [*] For positive integers u,v we have (u,v) = k
> iff there are positive coprime integers u' and v'
> with u = k u' and v = k v'.
>
> Suppose (a,b) = d and write a = d a' and b = d b' with (a' ,b') = 1.
very well
T
gcd(a,b)=c <=> En,m a=c*n /\ b=c*m /\ gcd(n,m)=1
yes
gcd(a,b)=c <=> Er,s a=c*r /\ b=c*s /\ gcd(r,s)=1
<=> Er^n,s^n a^n=c^n*r^n /\ b^n=c^n*s^n /\ gcd(r^n,s^n)=1
T
<=> gcd(a^n, b^n)=c^n
=> gcd(a^n, b^n)=(gcd(a,b))^n
you have only to prove
gcd(r,s)=1 <=> gcd(r^n,s^n)=1
but this last is easy
rio
"rio" <a@b.c> ha scritto nel messaggio
news:491dc4af$0$40309$4faf...@reader5.news.tin.it...
proposition
r,s,neN; gcd(r,s)=1 <=> gcd(r^n,s^n)=1
Dim
[=>]
gcd(r,s)=1 =>
gcd(r,s)=1 /\ gcd(r,s)=1 => gcd(r,s^2)=1 => gcd(s^2, r)=1
=> gcd(s^2, r)=1 /\ gcd(s^2, r)=1 => gcd(s^2, r^2)=1
=> gcd(r^2, s^2)=1
suppose i have
gcd(r^j, s^j)=1 =>
gcd(r^j, s^j)=1 /\ gcd(r^j, s^j)=1 => gcd(r^j, s^(j+1))=1 =>
gcd(s^(j+1), r^j)=1 =>
gcd(s^(j+1), r^j)=1 /\ gcd(s^(j+1), r^j)=1 => gcd(s^(j+1), r^(j+1))=1
=> gcd(r^(j+1), s^(j+1))=1
for indution => (AneN gcd(r,s)=1 => gcd(r^n,s^n)=1)
[<=]
Div==Divisors
gcd(r^n,s^n)=1 =>
Def
1=gcd(r^n,s^n) = Max(Div(r^n) inter Div(s^n))
Div(r) c Div(r^n) /\ Div(s) c Div(s^n) =>
(Div(r) intersetion Div(s) ) is subset or = (Div(r^n) intersetion Div(s^n) )
1<= Max(Div(r) intersetion Div(s) ) <= Max(Div(r^n) intersetion Div(s^n) ) =
= gcd(r^n,s^n)=1
=> gcd(r,s)= Max(Div(r) intersetion Div(s) )=1
end
rio
"rio" <a@b.c> ha scritto nel messaggio
>
> proposition
> r,s,neN; gcd(r,s)=1 <=> gcd(r^n,s^n)=1
> Dim
> [=>]
> gcd(r,s)=1 =>
> gcd(r,s)=1 /\ gcd(r,s)=1 => gcd(r,s^2)=1 => gcd(s^2, r)=1
> => gcd(s^2, r)=1 /\ gcd(s^2, r)=1 => gcd(s^2, r^2)=1
> => gcd(r^2, s^2)=1
> suppose i have gcd(r^j, s^j)=1 =>
> gcd(r^j, s^j)=1 /\ gcd(r^j, s^j)=1 => gcd(r^j, s^(j+1))=1 =>
wrong i don't know gcd(r^j, s)=1
Tim Smith
William Elliot <ma...@rdrop.remove.com> wrote:
> Apparently if a,b,n in N, then
> (a,b)^n = (a^n, b^n).
>
> Is that correct? If so, how does one prove it?
A remarkable (at least it seems so to me) result follows from that:
Let d = smallest positive integer of the form a x + b y.
Let D = smallest positive integer of the form a^n u + b^n v.
Then d^n = D.
I find that remarkable because it isn't even apparent (at least to me)
that (ax+by)^n is a linear combination of a^n, b^n. It looks like
(ax+by)^n should have all kinds of other powers of a and b. But for the
special values of x and y that minimize d, those must all add up in such
a way to get multiples of a^n or b^n.
--
--Tim Smith
rio
"rio" <a@b.c> ha scritto nel messaggio
news:491dc4af$0$40309$4faf...@reader5.news.tin.it...
no proof
> yes
>
> gcd(a,b)=c <=> Er,s a=c*r /\ b=c*s /\ gcd(r,s)=1
> <=> Er^n,s^n a^n=c^n*r^n /\ b^n=c^n*s^n /\ gcd(r^n,s^n)=1
> T
> <=> gcd(a^n, b^n)=c^n
>
> => gcd(a^n, b^n)=(gcd(a,b))^n
>
> you have only to prove
> gcd(r,s)=1 <=> gcd(r^n,s^n)=1
>
> but this last is easy
Div==Divisors
/*\==intersetion of sets
E == exist
A == for all
e == is element in the set
c == is subset
^ == pow
/\ == and
\/ == or
Proposition 0
r,s,neN; gcd(r,s)=1 /\ gcd(r,n)=1 => gcd(r,s*n)=1
Dim
r,s,neN; gcd(r,s)=1 /\ gcd(r,n)=1 =>
Max(Div(r)/*\Div(s))=1 /\ Max(Div(r)/*\Div(n))=1 =>
Div(r)/*\Div(s)={1} /\ Div(r)/*\Div(n)={1}
=> Div(r)/*\Div(s*n)={1} [don't know]
[if p is prime and p|r /\ p|s*n =>
/ p|s => p|r/\p|s /\ Div(r)/*\Div(s)={1} => p=1
\/ <
\ p|n => p|r/\p|n /\ Div(r)/*\Div(n)={1} => p=1
=> p=1
]
=> gcd(r,s*n)=Max(Div(r)/*\Div(s*n))=1
Proposition 1
r,s,neN; gcd(r,s)=1 => gcd(r,s^n)=1
Dim
r,s,neN;
gcd(r,s)=1
gcd(r,s^j)=1 => gcd(r,s^j)=1 /\ gcd(r,s)=1
=> gcd(r, s^(j+1))=1
for indution ok
Proposition 2
r,s,neN; gcd(r,s)=1 <=> gcd(r^n,s^n)=1
Dim
r,s,neN;
[=>]
gcd(r,s)=1 => gcd(r,s^n)=1 => gcd(s^n, r)=1
=> gcd(s^n, r^n)=1 => gcd(r^n, s^n)=1
[<=]
gcd(r^n,s^n)=1 =>
Def
1=gcd(r^n,s^n) = Max(Div(r^n) /*\ Div(s^n))
Div(r) c Div(r^n) /\ Div(s) c Div(s^n) =>
(Div(r) intersetion Div(s) ) is subset or = (Div(r^n) intersetion Div(s^n) )
1<= Max(Div(r) intersetion Div(s) ) <= Max(Div(r^n) intersetion Div(s^n) ) =
= gcd(r^n,s^n)=1
=> gcd(r,s)= Max(Div(r) intersetion Div(s) )=1
Proposition 3
a,b,neN gcd(a^n, b^n)=(gcd(a,b))^n
Dim
gcd(a,b)=c <=> Er,s a=c*r /\ b=c*s /\ gcd(r,s)=1
<=> Er^n,s^n a^n=c^n*r^n /\ b^n=c^n*s^n /\ gcd(r^n,s^n)=1
William Elliot
>
>> If n in N, q in Q and q^n in N, then q in Z.
>
> I came up with a proof of this a few years back. My proof only discussed
> n=2, but would be equally valid for any n in N+. (Note that the theorem
> is false for n=0).
>
> I found this a much more appealing proof of the irrationality of
> sqrt(2) than the classic one.
>
a^n | b^n ==> a | b.
As a corollary, if k in N, then
k^(1/n) in Q iff some j in N with k = j^n.
Fanstasic how far reaching this direct method is.
William Elliot
>
> To prove (a, b)^n = (a^n, b^n),
> without prime factorization,
> use the following fact:
>
> [*] For positive integers u,v we have (u,v) = k
> iff there are positive coprime integers u' and v'
> with u = k u' and v = k v'.
>
u' = u/(u,v), v' = v/(u,v); k = (u,v)
> Suppose (a,b) = d and write a = d a' and b = d b' with (a' ,b') = 1.
r = a/(a,b); s = b/(a,b); a = r(a,b); b = s(a,b); (r,s) = 1
> Then a^n = d^n * a' ^ n and b^n = d^n * b' ^ n.
a^n = r^n (a,b)^n; b^n = s^n (a,b)^n
> Since (a', b') = 1 one has also (a' ^ n, b' ^ n) = 1.
(r^n, s^n) = 1 iff (r,s) = 1
> Therefore using [*] we get (a^n, b^n) = d^n.
>
(a^n, b^n) = (r^n (a,b)^n, s^n (a,b)^n)
= (r^n, s^n).(a,b)^n = (a,b)^n
Thanks. I knew is was something like that but just couldn't find it.
Bill Dubuque
>
> (a,b)^n = (a^n, b^n) for a,b,n in N, (x,y) := gcd(x,y)
>
> Is that correct? If so, how does one prove it?
(A + B)^n = A^n + B^n, the so-called "Freshman's Dream" binomial theorem,
is true for both arithmetic of gcds and invertible ideals simply because
in both cases, multiplication is cancellative and addition is idempotent,
i.e. A + A = A for ideals, (A,A) = A for gcds. Combining this with the
associative, commutative, distributive laws of addition & multiplication
we obtain a very simple high-school-level proof of the Freshman's Dream:
e.g. (A + B)^4 = A^4 + A^3 B + A^2 B^2 + AB^3 + B^4
= A^2 (A^2 + AB + B^2) + (A^2 + AB + B^2) B^2
= (A^2 + B^2) (A + B)^2
=> (A + B)^2 = A^2 + B^2 if A + B is cancellable
Thus (A + B)^2n = A^n (A^n +...+ B^n) + (A^n +...+ B^n) B^n
= (A^n + B^n) (A + B)^n
=> (A + B)^n = A^n + B^n if A + B is cancellable QED
In the gcd case A+B := (A,B) = gcd(A,B) for A,B in a gcd-domain,
i.e. a domain where gcd(A,B) exists for all A,B != 0,0. Hence
Dream is true since (A,B) is cancellable, being non0 in a domain,
In a domain, non0 principal ideals are cancellable, so Dream is true
for ideals in a PID (e.g. Z), or fin. gen. ideals in a Bezout domain.
More generally, Dream also holds true in any Dedekind domain (e.g.
any number ring) since non0 ideals are invertible hence cancellable.
I've never seen this simple proof published anywhere, but probably
it is a folklore result that is well-known to some ring theorists.
Dream is true for all f.g. (finitely generated) ideals in domain D
iff every non0 f.g. ideal is invertible. Such domains are known as
Prufer domains. They're non-Noetherian generalizations of Dedekind
domains. Moreover they form an important class of domains because
they may also be equivalently characterized by a large number of
other important properties, e.g. they are precisely the domains
satisfying CRT (Chinese Remainder Theorem); Gauss's Lemma: the
content ideal c(fg) = c(f)c(g); non0 f.g. ideals are cancellable;
f.g. ideals satisfy contains => divides; etc. It's been estimated
that there are close to a hundred such characterizations known.
Below are some of the most well-known characterizations:
THEOREM Let D be a domain. The following conditions are equivalent:
(1) D is a Prufer domain, i.e. every non0 f.g. ideal is invertible
(2) Every non0 two-generated ideal of D is invertible.
(3) D_P is a Prufer domain for every prime ideal P of D.
(4) D_P is a valuation domain for every prime ideal P of D.
(5) D_P is a valuation domain for every maximal ideal P of D.
(6) non0 f.g. ideals I are cancellable: IJ = IK => J = K
(7) (6) restricted to f.g. J,K.
(8) D is integrally closed and there is an integer n > 1 such that
for every two elements a,b in D, (a,b)^n = (a^n,b^n).
(9) D is integrally closed and there is an integer n > 1 such that
for every two elements a,b in D, a^(n-1) b in (a^n, b^n).
(10) Each ideal I of D is complete, that is I = /\ IV_j as V_j run
over all the valuation overrings of D.
(11) Each f.g. ideal of D is an intersection of valuation ideals.
(12) If I,J,K are non0 ideals of D, then I /\ (J + K) = I/\J + I/\K
(13) If I,J,K are non0 ideals of D, then I (J /\ K) = IJ /\ IK.
(14) If I,J are non0 ideals of D, then (I + J)(I /\ J) = IJ.
(15) If I,J are non0 ideals of D, and K is a non0 f.g. ideal of D,
then (I + J):K = I:K + J:K.
(16) For any two elements a,b in D, (a:b) + (b:a) = D.
(17) If I,J are two non0 f.g. ideals of D, and K is a non0 ideal of D,
then K:(I /\ J) = K:I + K:J.
(18) D is integrally closed and each overring of D is the intersection
of localizations of D.
(19) D is integrally closed and each overring of D is the intersection
of quotient rings of D.
(20) Each overring of D is integrally closed.
(21) Each overring of D is flat over D.
(22) D is integrally closed and the prime ideals of any overring of D
are extensions of the prime ideals of D.
(23) D is integrally closed and for each prime ideal P of D, and each
overring S of D, there is at most one prime ideal of S lying over P.
(24) For any two polynomials f and g in D[x], c(fg) = c(f) c(g); where
for a polynomial h in D[x], c(h) denotes the ideal of D generated
by the coefficients of h. (Gauss' Lemma)
(25) Ideal in D are integrally closed.
(26) If I,J are ideals with I f.g. then I>J => I|J.
(27) D satisfies the CRT (Chinese Remainder Theorem), i.e. a system of
congruences x = xj (mod Ij) is solvable iff xj = xk (mod Ij + Ik).
--Bill Dubuque