Factorial Way

Number Theory Level pending

For each positive integer 'n', consider the highest common factor 'H' of the two numbers n!+1 and (n+1)!. for n<100, find the largest value of 'H'.


The answer is 97.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Brian Moehring
Aug 16, 2018

Using the notation gcd ( x , y ) \gcd(x,y) to denote the greatest common divisor (a.k.a. highest common factor) of x x and y , y, we can write

H = gcd ( n ! + 1 , ( n + 1 ) ! ) = gcd ( n ! + 1 , n ! ( n + 1 ) ) = gcd ( n ! + 1 , n + 1 ) Since gcd ( n ! + 1 , n ! ) = 1 = { n + 1 if ( n + 1 ) is a prime 1 otherwise By Wilson’s theorem \begin{aligned} H &= \gcd(n!+1, (n+1)!) \qquad \qquad \\ &= \gcd(n!+1, n!(n+1)) \\ &= \gcd(n!+1,n+1) & \text{Since } \gcd(n!+1, n!) = 1 \\ &= \begin{cases}n+1 & \text{ if } (n+1) \text{ is a prime} \\ 1 & \text{ otherwise}\end{cases} & \text{By Wilson's theorem} \end{aligned}

The problem can then be rephrased to "What is the largest prime p = n + 1 100 p = n+1 \leq 100 ?" and therefore the answer is 97 \boxed{97}

I was drunk when I solved it, were u? :)

A Former Brilliant Member - 2 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...