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

]

February 21, 2014 at 5:42 am

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.