routine number-theory exercise

(n!+1, (n+1)!+1)=1. [For all n \in N.]

[Let n \in N.]
Suppose (n!+1, (n+1)!+1) = K > 1.
Then K has a prime divisor p>1.
We have p|(n!+1) and p|(n+1)!+1.
Since “p|x and p|y” implies that
“p|(y-x)” in all cases, we have
p|[ (n+1)!+1 – (n!+1) ]
p|[ (n+1)n! – n!]
p|n*n!.
But then (because p is prime) p|n!.
This is absurd since we also know p|n!+1.
No such p exists; K = 1; we are done.
[
i’ve been cranking out *lots* of number
theory problems… i’ve never taught the
subject at this level of detail and *need*
to do lots of problems (in order that
exercises like this can *become* “routine”.)
but i’ve only *typed up* a few (one
problem set [out of four that i’ve marked
so far]). anyhow, none of the class
had a proof this short-&-sweet so here
it is now for my loyal subscribers.
this is a *great* quarter so far.
getting back to work.
oops, “semester” so far.
\bye
]

Advertisements

  1. i like this one too.
    it’s quite a bit more “routine”, though.
    and… um… kinda *long*.
    Suppose
    (i) (a,b,c) = 10 = 2*5 and
    (ii) [a,b,c] = 100 = 2^2*5^2
    for some natural numbers a, b, and c.
    (We will enumerate all the possibilities.)
    Let A = a/10, B = b/10, and C = c/10.
    These are natural numbers (by (i)).
    We then have
    10*(A,B,C) = (a,b,c) = 10,
    and so
    (A,B,C)=1.
    By the same reasoning,
    [A,B,C]= (1/10)[a,b,c] = 10.
    So we will seek coprime triples A, B, C,
    satisfying [A, B, C] = 10. (Clearly we
    can then multiply by 10 to recover the
    “a, b, and c” of the problem statement.)
    For simplicity we’ll first consider triples
    having A \le B \le C
    (where “\le” denotes “is less than or equal to”).
    We need only consider divisors of 10:
    {A, B, C} \subset {1, 2, 5, 10}.
    The “triples” A=B=C=10, A=B=C=5,
    and A=B=C=2 all fail to be coprime;
    A=B=C=1 fails at [A,B,C]=10.
    Any “triple” having A<B<C "works";
    there are obviously 4 of these
    ("leave out" one of 4 elements!):
    {1, 2, 5}, {1, 2, 10}, {1, 5, 10}, and {2, 5, 10}.
    Finally we must consider triples having exactly
    two distinct values. One simply checks each of
    the (six) possible pairs from {1, 2, 5, 10}:
    the two that "work" are {1, 10} and {2, 5}.
    Any of our A<B<C "triples" can be permuted in *six* ways:
    ABC, ACB, BAC, BCA, CAB, and CBA.
    But two-valued triples also present six possibilities each:
    1-1-10, 1-10-1, 10-1-1,
    1-10-10, 10-1-10, 1-1-10, for example.
    So we have 4*6 + 2*6 = 36 possibilities.
    Restoring the "10" of the original problem statement,
    we have that a-b-c is one of the objects listed below.
    10-20-50, 10-50-20, 20-10-50, 20-50-10, 50-10-20, 50-20-10,
    10-20-100, 10-100-20, 20-10-100, 20-100-10, 100-10-20, 100-20-10,
    10-50-100, 10-100-50, 50-10-100, 50-100-10, 100-10-50, 100-50-10,
    20-50-100, 20-100-50, 50-20-100, 50-100-20, 100-20-50, 100-50-20,
    10-10-100, 10-100-10, 100-10-10,
    10-100-100, 100-10-100, 100-100-10,
    20-20-50, 20-50-20, 50-20-20,
    20-50-50, 50-20-50, 50-50-20.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: