- - Divisibility (involving gcd's)
qsymmetry
then why is it true that, for all integers k,
m/(m, k) divides n/(n, k)
where (a, b) denotes the gcd of a and b ?
This seems intuitively obvious, but the proof is a bit of a pain to write down
Any help would be appreciated; thank you !
Arturo Magidin
I'm sure Bill Dubuque will post a simple and more elegant answer, but
you can just write it out. Let d = (m,k); m = de, k=df, (so (e,f)=1),
and n = ma = dea. Since d|k and d|n, then d|(k,n), and if (k,n) = dh,
then h must be relatively prime to e (otherwise, a common factor of h
and of e would divide both m and k, and so you would have that d is
not the gcd of m and k); hence h divides a. Thus, n/(n,k) is e*(a/h),
with a/h an integer, and so this is a multiple of e = m/(m,k).
--
Arturo Magidin
Musatov
Results 1 - 10 for If m, n are positive integers with m dividing n,
i.e. m |n, true k. (0.56 seconds)
Did you mean: If men are positive integers with m dividing n, i.e. m |
n, true k
Custom Search
- - Divisibility (involving gcd's) - sci.math | Google Groups2 posts -
1 author - Last post: yesterday
If m, n are positive integers with m dividing n, i.e. m |n,. then why
is it true that, for all integers k,. m/(m, k) divides n/(n, k) ...
[http://groups.google.com/group/sci.math/browse_thread/thread/
07e82febe9ab2135 ]
Element Operations Returns true if and only if the integer n is
divisible by the integer d; if true, ... base b of the positive
integer n i.e., the largest integer k such that bk ≤n. ... upon
dividing the integer m by the integer n, that is, m = q.n + r, ...
[http://magma.maths.usyd.edu.au/magma/htmlhelp/text257.htm]
Math Forum - Ask Dr. Math Feb 13, 2003 ... For integers m and n,
define m~n if n|m^k and m|n^k for some positive integers j and k. ...
m~n if n|m^k and m|n^k for some positive integers j and k. a) ...
true, i.e.: m = p^a * m' n = p^b * n' and p divides neither m' nor
n'. ... Now, this implies that p_i | n, because, if p_i did not divide
n, ...
[http://mathforum.org/library/drmath/view/62242.html]
[ref] 15 Number Theorygap> l:= LogMod( 2, 5, 7 ); 5^l mod 7 = 2; 4
true gap> LogMod( 1, 3, ... If n is a quadratic residue modulo m ,
i.e., if there exists an r such that r2 ... n modulo the positive
integer m , i.e., a r such that rk ≡ n mod m . If .... Let a be the
product of all maximal powers of primes of the form 4k+3 dividing
n . ...
[http://www.gap-system.org/Manuals/doc/htm/ref/CHAP015.htm]
Gauss' Lemma Without Explicit Divisibility Arguments
It follows that N' = N [sqrt(C) - M] is a positive integer less than
N, and clearly N' sqrt(C) ... We know that r^(k-1) is not an integer,
so there must exist an integer M such that 0 < [r^(k-1) ... of r does
not divide 1, which is certainly true if the denominator is greater
than 1, i.e., if r is not an integer. ...
[http://www.mathpages.com/home/kmath118.htm]
[PDF] DivisibilityFile Format: PDF/Adobe Acrobat - View as HTML
school — namely, that you can divide one integer by another. .... If m
and n are integers and m = 0, then m divides n if mk = n for some
integer k. ... a complete sentence that can be true or false — it's an
expression. ... m and n are positive integers. Thus, k ≥ 1, and
multiplying both sides of this inequality ...
[http://marauder.millersville.edu/~bikenaga/abstractalgebra/
divisibility/divisibility.pdf]
[PDF] Problem Set #7 SolutionsFile Format: PDF/Adobe Acrobat - View as
HTML
But one of k and k + 1 is even, so there is an integer m such that k(k
+ 1) = 2m. So n. 2. = 4(2m) + 1 n. 2. = 8m + 1. So 8 | (n. 2. – 1),
i.e., n ...
[http://www.stanford.edu/class/cs103a/handouts/
46%20PS7%20Solutions.pdf]
[PDF] UMASS AMHERST MATH 471 FALL 2006, F. HAJIR NAME: Solvatum
Numerore
FALSE, (but true if m is prime.) c. If n > 1, then n is prime if and
only if for all integers a ... For each positive integer k, there
exists an integer N ... are pairwise inequivalent modulo m, i.e. for 1
≤ i < j ≤ e, .... but q does not divide a − 1. Show that q = 1 + kp
for some integer k and then show that ...
[http://www.math.umass.edu/~hajir/m471/m471ex2-sol.pdf]
Smarandache multiplicative functions
Largest mth power-free number dividing n (Smarandache mth power
residues) ... if xm is divisible by n or in other words a multiple of
Hm(n), i.e. x is ... All this leaves two slightly different functions
to be considered: Km(n) and Lm(n). ... Neil Sloane's Online
Encylopedia of Integer Sequences for m=2, 3 and 4: ...
[http://www.gallup.unm.edu/~smarandache/Bottomley-Sm-Mult-
Functions.htm]
by SSTM FUNCTIONS
Part 1: Basic PropositionsIf N is composite (i.e., if k > 1) then
there are positive integers a,b such ... only be true if M = N,
contradicting the assumption that M and N are co-prime.à ... Dividing
both sides by gcd(M,N) and expanding the x functions by the ...
[http://www.mathpages.com/home/kmath006/part1/part1.htm]
Rob Johnson
qsymmetry <qsym...@email.com> wrote:
>If m, n are positive integers with m dividing n, i.e. m |n,
>
>then why is it true that, for all integers k,
>
>
>m/(m, k) divides n/(n, k)
>
>where (a, b) denotes the gcd of a and b ?
>
>
>
>This seems intuitively obvious, but the proof is a bit of a pain to write down
Since m|n, we can write n = qm.
Claim: (qm,k) | (q,k) (m,k)
Proof: Using Bezout, we can write
(q,k) = q x1 + k y1
(m,k) = m x2 + k y2
Multiplying these, we get
(q,k) (m,k)
= (q x1 + k y1) (m x2 + k y2)
= qm (x1 x2) + k (m x2 y1 + q x1 y2 + k y1 y2)
Obviously, (qm,k) divides this.
QED
qm q m (q,k) (m,k)
------ = ----- ----- -----------
(qm,k) (q,k) (m,k) (qm,k)
Writing n = qm, we get
n m q (q,k) (m,k)
----- = ----- ( ----- ----------- )
(n,k) (m,k) (q,k) (qm,k)
This shows that m/(m,k) divides n/(n,k).
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
qsymmetry
> wrote:
> > If m, n are positive integers with m dividing n,
> i.e. m |n,
> >
> > then why is it true that, for all integers k,
> >
> > m/(m, k) divides n/(n, k)
> >
> > where (a, b) denotes the gcd of a and b ?
> >
> > This seems intuitively obvious, but the proof is a
> bit of a pain to write down
> >
> > Any help would be appreciated; thank you !
>
> I'm sure Bill Dubuque will post a simple and more
> elegant answer, but
> you can just write it out. Let d = (m,k); m = de,
> k=df, (so (e,f)=1),
> and n = ma = dea. Since d|k and d|n, then d|(k,n),
> and if (k,n) = dh,
> then h must be relatively prime to e (otherwise, a
> common factor of h
> and of e would divide both m and k,
how?
qsymmetry
> <30283047.5063.1245202251153.JavaMail.jakarta@nitrogen
This makes perfect sense! Thanks much, Rob!
Arturo Magidin
> > On Jun 16, 8:30 pm, qsymmetry <qsymme...@email.com>
> > wrote:
> > > If m, n are positive integers with m dividing n,
> > i.e. m |n,
>
> > > then why is it true that, for all integers k,
>
> > > m/(m, k) divides n/(n, k)
>
> > > where (a, b) denotes the gcd of a and b ?
>
> > > This seems intuitively obvious, but the proof is a
> > bit of a pain to write down
>
> > > Any help would be appreciated; thank you !
>
> > I'm sure Bill Dubuque will post a simple and more
> > elegant answer, but
> > you can just write it out. Let d = (m,k); m = de,
> > k=df, (so (e,f)=1),
> > and n = ma = dea. Since d|k and d|n, then d|(k,n),
> > and if (k,n) = dh,
> > then h must be relatively prime to e (otherwise, a
> > common factor of h
> > and of e would divide both m and k,
>
> how?
What do you mean, how?
You have m = de, k = df, and (e,f) = 1. Sinc eyou also know that dh
divides k, you have that k = dhg (that is, hg=f); if q is a common
factor of both h and e, then dq divides both d and m, and so by
definition of the gcd you have dq|d, hence q=1.
--
Arturo Magidin
qsymmetry
Thank you!
Bill Dubuque
>qsymmetry <qsym...@email.com> wrote:
>>
>> Prove m|n => m/(m,k) | n/(n,k)
>
> Since m|n, we can write n = qm.
>
> Claim: (qm,k) | (q,k) (m,k)
>
> Proof: Using Bezout, we can write
>
> (q,k) = q x1 + k y1
>
> (q,k) (m,k) = (q x1 + k y1) (m x2 + k y2)
>
> = qm (x1 x2) + k (m x2 y1 + q x1 y2 + k y1 y2)
>
> Obviously, (qm,k) divides this. QED
>
> So ----- = ------ = ----- ----- -----------
> (n,k) (qm,k) (q,k) (m,k) (qm,k)
SIMPLER (n,k)| n,kq
=> (n,k)|(n,kq) = q(m,k) QED
Generally (a,b)|(A,B) if a|A , b|B
i.e. d|(A,B) via d|a|A, d|b|B
Yet again [1,2] you've obfuscated a trivial proof by
unnecessarily inlining grotesque Bezout identities.
>
>[...] take out the trash before replying
Take out the Bezout trash before posting!
See also the parallel thread [3] on Ask An Algebraist.
--Bill Dubuque
[1] 18 May 2009 http://google.com/group/sci.math/msg/5ce760473f5d4399
http://google.com/groups?selm=y8z3ab1hnm4.fsf%40nestle.csail.mit.edu
[2] 22 Jul 2006 http://google.com/group/sci.math/msg/ae5b30ca22865a87
http://google.com/groups?selm=y8zzmf2xg5q.fsf%40nestle.csail.mit.edu
[3] http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist;task=show_msg;msg=1787.0001.0001
Bill Dubuque
>On Jun 16, 8:30�pm, qsymmetry <qsymme...@email.com> wrote:
>>
>
> you can just write it out. Let d = (m,k); m = de, k=df, (so (e,f)=1),
> and n = ma = dea. Since d|k and d|n, then d|(k,n), and if (k,n) = dh,
> then h must be relatively prime to e (otherwise, a common factor of h
> and of e would divide both m and k, and so you would have that d is
> not the gcd of m and k); hence h divides a. Thus, n/(n,k) is e*(a/h),
> with a/h an integer, and so this is a multiple of e = m/(m,k).
Wow, you've certainly got the heads spinning on those pesky mosquitos
after firing that barrage of extraneous variables at them. What a tour
de force - almost half the alphabet's in action. Who needs canonballs? :-)
See my prior post for a simpler proof using (a,b)|(A,B) if a|A, b|B.
Rob Johnson
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>r...@trash.whim.org (Rob Johnson) wrote:
>>qsymmetry <qsym...@email.com> wrote:
>>>
>>> Prove m|n => m/(m,k) | n/(n,k)
>>
>> Since m|n, we can write n = qm.
>>
>> Claim: (qm,k) | (q,k) (m,k)
>>
>> Proof: Using Bezout, we can write
>>
>> (q,k) = q x1 + k y1
>> (m,k) = m x2 + k y2 Multiplying,
>>
>> (q,k) (m,k) = (q x1 + k y1) (m x2 + k y2)
>>
>> = qm (x1 x2) + k (m x2 y1 + q x1 y2 + k y1 y2)
>>
>> Obviously, (qm,k) divides this. QED
>>
>> n qm q m (q,k) (m,k)
>> So ----- = ------ = ----- ----- -----------
>> (n,k) (qm,k) (q,k) (m,k) (qm,k)
>
>SIMPLER (n,k)| n,kq
>
> => (n,k)|(n,kq) = q(m,k) QED
It is not clear what is being proved.
q is a multiple of (q,k), so what is shown above is that (n,k)
divides a multiple of (q,k) (m,k). This does not show that (n,k)
divides (q,k) (m,k). This is evidently not the aim.
Using q = n/m, what is shown above says (n,k) | n/m (m,k), which can
be rewritten as m/(m,k) | n/(n,k). I assume that this is the second
half of what was intended.
>
>Generally (a,b)|(A,B) if a|A , b|B
>
> i.e. d|(A,B) via d|a|A, d|b|B
True, but how does this apply to the problem at hand? Since m|n and
k|k, this shows that (m,k)|(n,k). However, this is the opposite
direction of what is needed for the problem at hand.
>Yet again [1,2] you've obfuscated a trivial proof by
>unnecessarily inlining grotesque Bezout identities.
>>
>>[...] take out the trash before replying
>
>Take out the Bezout trash before posting!
I agree that what you wrote is the beginning of a shorter and simpler
proof. However, that does not mean that everything else is trash.
No matter how much better a proof I think I have than someone else,
I try to appreciate another proof as simply a different approach.
Besides, this gives you a chance to augment your bibliography for the
next post in which I use Bezout's Identity.
>See also the parallel thread [3] on Ask An Algebraist.
>
>--Bill Dubuque
>
>[1] 18 May 2009 http://google.com/group/sci.math/msg/5ce760473f5d4399
>http://google.com/groups?selm=y8z3ab1hnm4.fsf%40nestle.csail.mit.edu
>
>[2] 22 Jul 2006 http://google.com/group/sci.math/msg/ae5b30ca22865a87
>http://google.com/groups?selm=y8zzmf2xg5q.fsf%40nestle.csail.mit.edu
>
>[3] http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist;task=show_msg;msg=1787.0001.0001
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>r...@trash.whim.org (Rob Johnson) wrote:
>>>qsymmetry <qsym...@email.com> wrote:
>>>>
>>>> Prove m|n => m/(m,k) | n/(n,k)
>>>
>>> Since m|n, we can write n = qm.
>>>
>>> Claim: (qm,k) | (q,k) (m,k)
>>>
>>> Proof: Using Bezout, we can write
>>>
>>> (q,k) = q x1 + k y1
>>> (m,k) = m x2 + k y2 Multiplying,
>>>
>>> (q,k) (m,k) = (q x1 + k y1) (m x2 + k y2)
>>>
>>> = qm (x1 x2) + k (m x2 y1 + q x1 y2 + k y1 y2)
>>>
>>> Obviously, (qm,k) divides this. QED
>>>
>>> n qm q m (q,k) (m,k)
>>> So ----- = ------ = ----- ----- -----------
>>> (n,k) (qm,k) (q,k) (m,k) (qm,k)
>>
>> SIMPLER (n,k)| n,kq
>>
>> => (n,k)|(n,kq) = q(m,k) QED
>
> It is not clear what is being proved.
I proved that N|nM/m, N=(n,k), M=(m,k)
Sought is m/M|n/N in the OPs problem.
Both are <=> mN|nM via scale by m, MN resp.
One quickly "sees" such equivalences purely mentally.
> q is a multiple of (q,k), so what is shown above is that (n,k)
> divides a multiple of (q,k) (m,k). This does not show that (n,k)
> divides (q,k) (m,k). This is evidently not the aim.
My aim was to prove the inference sought by the OP, not your "Claim".
But that too can be proved more elegantly if so desired.
> Using q = n/m, what is shown above says (n,k) | n/m (m,k), which can
> be rewritten as m/(m,k) | n/(n,k). I assume that this is the second
> half of what was intended.
I proved the inference sought by the OP. It has no "second half".
>>Generally (a,b)|(A,B) if a|A , b|B
>>
>> i.e. d|(A,B) via d|a|A, d|b|B
>
> True, but how does this apply to the problem at hand? Since
> m|n and k|k, this shows that (m,k)|(n,k). However, this is the
> opposite direction of what is needed for the problem at hand.
No, my proof is the special case a,b, A,B = n,k, n,kq
My point is that by scaling the problem reduces to
said standard obvious gcd divisibility property.
>>Yet again [1,2] you've obfuscated a trivial proof by
>>unnecessarily inlining grotesque Bezout identities.
>>>
>>>[...] take out the trash before replying
>>
>>Take out the Bezout trash before posting!
>
> I agree that what you wrote is the beginning
> of a shorter and simpler proof.
It's a complete one-line proof. Hopefully you see it now.
> However, that does not mean that everything else is trash.
> No matter how much better a proof I think I have than someone else,
> I try to appreciate another proof as simply a different approach.
But you continue to obfuscate simple number theory proofs by littering
them with inlined Bezout identities even after I've shown you better
ways on numerous occasions (e.g. in the threads linked below). It's
important to recognize such simplifications in simpler scenarios
if one is ever to have any hope of conquering more complex problems.
> Besides, this gives you a chance to augment your bibliography
> for the next post in which I use Bezout's Identity.
You seem to be more of an analyst than an algebraist / number theorist.
In algebra, and esp. in number theory, there is often more opportunity
to "polish" proofs - to eliminate the messy calculations - to reduce
to the bare essence of the matter. I suppose that analysts have given
up on such because analytic proofs are often (intrinsically?) littered
with many messy calculations on inequalities etc. This might help to
explain somewhat the differences in our viewpoints.
Rob Johnson
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>r...@trash.whim.org (Rob Johnson) wrote:
>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>r...@trash.whim.org (Rob Johnson) wrote:
>>>>qsymmetry <qsym...@email.com> wrote:
>>>>>
>>>>> Prove m|n => m/(m,k) | n/(n,k)
>>>>
>>>> Since m|n, we can write n = qm.
>>>>
>>>> Claim: (qm,k) | (q,k) (m,k)
>>>>
>>>> Proof: Using Bezout, we can write
>>>>
>>>> (q,k) = q x1 + k y1
>>>> (m,k) = m x2 + k y2 Multiplying,
>>>>
>>>> (q,k) (m,k) = (q x1 + k y1) (m x2 + k y2)
>>>>
>>>> = qm (x1 x2) + k (m x2 y1 + q x1 y2 + k y1 y2)
>>>>
>>>> Obviously, (qm,k) divides this. QED
>>>>
>>>> n qm q m (q,k) (m,k)
>>>> So ----- = ------ = ----- ----- -----------
>>>> (n,k) (qm,k) (q,k) (m,k) (qm,k)
>>>
>>> SIMPLER (n,k)| n,kq
>>>
>>> => (n,k)|(n,kq) = q(m,k) QED
>>
>> It is not clear what is being proved.
>
>I proved that N|nM/m, N=(n,k), M=(m,k)
>
>Sought is m/M|n/N in the OPs problem.
>
>Both are <=> mN|nM via scale by m, MN resp.
>
>One quickly "sees" such equivalences purely mentally.
Perhaps, but if someone is asking for a proof of an elementary fact,
they might appreciate seeing these equivalences explicitly listed.
Once you see them, they are obvious, but a proof is not always for
those for whom it is obvious.
>> q is a multiple of (q,k), so what is shown above is that (n,k)
>> divides a multiple of (q,k) (m,k). This does not show that (n,k)
>> divides (q,k) (m,k). This is evidently not the aim.
>
>My aim was to prove the inference sought by the OP, not your "Claim".
>But that too can be proved more elegantly if so desired.
Yes, I did see that, but at first I thought you were trying to prove
the claim (no deprecative quotes), and when I saw that that did not
apply, I knew you must have meant to answer the original question.
>> Using q = n/m, what is shown above says (n,k) | n/m (m,k), which can
>> be rewritten as m/(m,k) | n/(n,k). I assume that this is the second
>> half of what was intended.
>
>I proved the inference sought by the OP. It has no "second half".
>
>>>Generally (a,b)|(A,B) if a|A , b|B
>>>
>>> i.e. d|(A,B) via d|a|A, d|b|B
>>
>> True, but how does this apply to the problem at hand? Since
>> m|n and k|k, this shows that (m,k)|(n,k). However, this is the
>> opposite direction of what is needed for the problem at hand.
>
>No, my proof is the special case a,b, A,B = n,k, n,kq
>
>My point is that by scaling the problem reduces to
>said standard obvious gcd divisibility property.
>
>>>Yet again [1,2] you've obfuscated a trivial proof by
>>>unnecessarily inlining grotesque Bezout identities.
>>>>
>>>>[...] take out the trash before replying
>>>
>>>Take out the Bezout trash before posting!
>>
>> I agree that what you wrote is the beginning
>> of a shorter and simpler proof.
>
>It's a complete one-line proof. Hopefully you see it now.
Your idea of a complete proof differs from mine. In my opinion,
you supplied the key step in a complete proof, but a complete proof
starts with the given and ends with the conclusion. The extra
equivalences (and the expansion of q = n/m) make the proof much
more accessible.
>> However, that does not mean that everything else is trash.
>> No matter how much better a proof I think I have than someone else,
>> I try to appreciate another proof as simply a different approach.
>
>But you continue to obfuscate simple number theory proofs by littering
>them with inlined Bezout identities even after I've shown you better
>ways on numerous occasions (e.g. in the threads linked below). It's
>important to recognize such simplifications in simpler scenarios
>if one is ever to have any hope of conquering more complex problems.
>
>> Besides, this gives you a chance to augment your bibliography
>> for the next post in which I use Bezout's Identity.
>
>You seem to be more of an analyst than an algebraist / number theorist.
>In algebra, and esp. in number theory, there is often more opportunity
>to "polish" proofs - to eliminate the messy calculations - to reduce
>to the bare essence of the matter. I suppose that analysts have given
>up on such because analytic proofs are often (intrinsically?) littered
>with many messy calculations on inequalities etc. This might help to
>explain somewhat the differences in our viewpoints.
Indeed, I am an analyst, and I find some of the polished proofs less
accessible. That is, while each step follows logically from the next,
it is hard to understand what is really going on, or to see how the
author was motivated to get from one step to the next. I'm not saying
that this is the case here, but in a number of polished proofs it is.
>>>See also the parallel thread [3] on Ask An Algebraist.
>
>--Bill Dubuque
>
>[1] 18 May 2009 http://google.com/group/sci.math/msg/5ce760473f5d4399
>http://google.com/groups?selm=y8z3ab1hnm4.fsf%40nestle.csail.mit.edu
>
>[2] 22 Jul 2006 http://google.com/group/sci.math/msg/ae5b30ca22865a87
>http://google.com/groups?selm=y8zzmf2xg5q.fsf%40nestle.csail.mit.edu
>
>[3] http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist;task=show_msg;msg=1787.0001.0001
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>r...@trash.whim.org (Rob Johnson) wrote:
>>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>>r...@trash.whim.org (Rob Johnson) wrote:
>>>>>qsymmetry <qsym...@email.com> wrote:
>>>>>>
>>>>>> Prove m|n => m/(m,k) | n/(n,k)
>>>>>
>>>>> Since m|n, we can write n = qm.
>>>>>
>>>>> Claim: (qm,k) | (q,k) (m,k)
>>>>>
>>>>> Proof: Using Bezout, we can write
>>>>>
>>>>> (q,k) = q x1 + k y1
>>>>> (m,k) = m x2 + k y2 Multiplying,
>>>>>
>>>>> (q,k) (m,k) = (q x1 + k y1) (m x2 + k y2)
>>>>>
>>>>> = qm (x1 x2) + k (m x2 y1 + q x1 y2 + k y1 y2)
>>>>>
>>>>> Obviously, (qm,k) divides this. QED
>>>>>
>>>>> n qm q m (q,k) (m,k)
>>>>> So ----- = ------ = ----- ----- -----------
>>>>> (n,k) (qm,k) (q,k) (m,k) (qm,k)
>>>>
>>>> SIMPLER (n,k)| n,kq
>>>>
>>>> => (n,k)|(n,kq) = q(m,k) QED
>>>
>>> It is not clear what is being proved.
>>
>>I proved that N|nM/m, N=(n,k), M=(m,k)
>>
>>Sought is m/M|n/N
>>
>>
>>One quickly "sees" such equivalences purely mentally.
>
> Perhaps, but if someone is asking for a proof of an elementary fact,
> they might appreciate seeing these equivalences explicitly listed.
> Once you see them, they are obvious, but a proof is not always for
> those for whom it is obvious.
The omitted divisibility equivalence is equivalent to the following
fraction equality (nM/m)/N = (n/N)/(m/M). If a student can't quickly
see this then they're ill-prepared to study elementary number theory.
>>It's a complete one-line proof. Hopefully you see it now.
>
> Your idea of a complete proof differs from mine. In my opinion,
> you supplied the key step in a complete proof, but a complete proof
> starts with the given and ends with the conclusion. The extra
> equivalences (and the expansion of q = n/m) make the proof much
> more accessible.
The QED implicitly implies that the proof is complete and, hence,
that the divisibility relation proved is equivalent to that sought.
As I said, checking this requires simply checking a fraction equality.
Such trivial arithmetic is better omitted so as not to obscure the
essence of the proof - which here is that (a,b)|(A,B) if a|A, b|B.
--Bill Dubuque