### 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
]

#### 1 Comment

1. vlorbik

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.

• ## (Partial) Contents Page

Vlorbik On Math Ed ('07—'09)
(a good place to start!)