"A First Course in Number Theory" discussion group

[R.D. Silverman]

Originally Posted by owftheevil

Its easy to define a well ordering on the rationals. For the reals, it depends on if you believe the axiom of choice or not.

I think that "believe" is the wrong choice of words. I'd rather say "accept". [I do accept AC]

I'm not quite sure what you are getting at with the question about the non transitivity of the "not divides" relation. If someone were mistakenly to believe it, they could construct some easy proofs of untrue things. But then, that's true whenever you start with a false assumption. I doubt this is what you are after though because you are usually more subtle than that.

I am just hoping to provoke a discussion regarding an elementary topic.

Note that there is some relevance to determination of the GCD of an arbitrary SET of integers and whether pairwise co-prime
means set-wise co-prime.

[R.D. Silverman]

Originally Posted by MattcAnderson

Hi Math People

Continuing to work through the first chapter. I read problem 2c)
Express G as an integral linear combination of b and c for the following triples of positive integers -

c) G = 17; b = 3587; c = 1819;

I assume we want to solve

17 = A*1819 + B*3587

Consulting wolframalpha.com I find that A = 211n + 71 and B = -107n - 36
This is of course a line.
I let n be 0. Then we have
17 = 71*1819 - 36*3587.
This is the end of the problem 2c for me.

FAIL.

And what did you learn by having black box code do the problem for you?
Show us that you can do the problem with JUST pencil & paper.

Did you think that Wolfram Alpha just pulled the coefficients 36 and 71 from your ass?

Please compare with answer in the back.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Generally, when a college student lacks knowledge of one or more prerequisites he/she is expected
to either go out and learn the required background material on their own, *Or* come to office
hours. How should we handle "office hours" in this thread? Private emails would be OK
if not too large in number.

The question of what should be assumed herein is interesting. Just to pull a random thought
from <substitute one's favororite source>, does everyone understand what the contrapositive
of a statement is??? This is really basic stuff.

I'm sure that Wiki has decent explanations of both (induction/descent) concepts. Should we send people to Wiki?

Responses?????

[R.D. Silverman]

Originally Posted by R.D. Silverman

Responses?????

And some excellent side reading if people are interested:

http://www.de.ufpe.br/~toom/my-artic...c/ARUSSIAN.PDF

[wombatman]

Originally Posted by R.D. Silverman

And some excellent side reading if people are interested:

http://www.de.ufpe.br/~toom/my-artic...c/ARUSSIAN.PDF

I really enjoyed reading this. Another article along somewhat similar lines about the willingness to let students struggle:

http://ww2.kqed.org/mindshift/2012/1...tern-cultures/

[R.D. Silverman]

Originally Posted by R.D. Silverman

FAIL.

And what did you learn by having black box code do the problem for you?
Show us that you can do the problem with JUST pencil & paper.

Did you think that Wolfram Alpha just pulled the coefficients 36 and 71 from your ass?

Please compare with answer in the back.

BTW, you have already been shown within this thread how to answer this question.

[ewmayer]

As it happens I am currently in the process of upgrading my Lehmer-gcd code 'from O(n^2) midway to O(n (log n)^2)' by using 64-bit math to accumulate large-ish chunks of partial multipliers and then using FFT-muls to apply said multipliers to obtain the needed linear combinations which yield the next iteration's smaller-sized operands, so the above problem resonates.

[I say 'midway' because my first impl. of the FFT-mul will use fixed-sized FFT-muls to reduce the operand sizes by 64-80kbits at a time, thus will still be overall quadratic, but with a drastically smaller proportionality constant. That will still need added logic to effect the recursion needed to gain the desired asymptotic speedup].

[ewmayer]

Toom-problems split off into side discussion (I still need to work backward to move/copy remaining related posts) - please post any further comments on the Toom PDF there.

[bgbeuning]

Originally Posted by Xyzzy

Mr. Silverman has recommended this book for us to read to learn the basics of number theory.

http://www.amazon.com/First-Course-N.../dp/0534085148

We have ordered a copy. It looks like you can get one for around $15 shipped easily.

Amazon has this book for $673.14 .
I guess supply and demand does work.

[davar55]

I have no access to that book, but I'd like to follow along.
Perhaps I can learn something.

As for FTA and the preliminary lemma p | ab --> p | a ior p | b,
where are we?

I didn't fully catch the proof until sophomore year,
and it's not ingrained in my memory. I may have
to dredge it up if we follow RDS' leadership.

I'm all for this learning project.

[davar55]

Originally Posted by ewmayer

As it happens I am currently in the process of upgrading my Lehmer-gcd code 'from O(n^2) midway to O(n (log n)^2)' by using 64-bit math to accumulate large-ish chunks of partial multipliers and then using FFT-muls to apply said multipliers to obtain the needed linear combinations which yield the next iteration's smaller-sized operands, so the above problem resonates.

[I say 'midway' because my first impl. of the FFT-mul will use fixed-sized FFT-muls to reduce the operand sizes by 64-80kbits at a time, thus will still be overall quadratic, but with a drastically smaller proportionality constant. That will still need added logic to effect the recursion needed to gain the desired asymptotic speedup].

Cool. But your work is a long-term goal for us. Perhaps you'll join in
this teaching discussion on our more elementary level.