Factorial

mfgoode · 2007-07-20, 15:24

To me this is a tricky one. I think its for people of Alpertron's and Maxal's calibre. Anyway its open for one and all!

Show that 61! + 1 ==0 and 63! + 1 == 0 mod 71.

Take a shot at it though.

Mally

wpolly · 2007-07-20, 18:34

61!=(9!)^(-1) (mod 71)
63!=(7!)^(-1) (mod 71)
7!=-1 (mod 71)
9!=72*7!=-1 (mod 71)

alpertron · 2007-07-20, 20:26

More verbose solution:

According to Wilson's theorem (p-1)!+1 is divisible by p. Since 71 is prime, we have: 70!+1 = 0 (mod 71), which implies 70! = -1 (mod 71).

Now 61! = 70!/(70*69*68*67*...*61)

But 70 = -1, 69 = -2, 68 = -3, etc. (mod 71) so 70 * 69 * 68 *...*62 = -9! (mod 71) (because the number of factors is odd).

61! = 70!/(-9!) -> 61! = 1/9! (mod 71)

In the same way:

63! = 1/7! (mod 71)

Now notice that 7! = 5040 = 71^2-1 = -1 (mod 71).

So 63! = 1/(-1) = -1, then 63!+1 = 0 (mod 71)

9! = 9*8*7! = 72*7! = 1*7! = -1 (mod 71)

So 61! = 1/(-1) = -1, then 61!+1 = 0 (mod 71)

mfgoode · 2007-07-21, 15:42

Yeah wpolly and Alpertron thats about it! Good work, Thank you.

Mally

Jens K Andersen · 2007-07-23, 23:22

By the way, there are more congruent factorials modulo 71 than modulo any smaller prime. See http://primepuzzles.net/problems/prob_027.htm for more primes with many congruent factorials.
n! == 8978998 (mod 10428007), for n = 816488, 1251081, 3384225, 4112650, 4237275, 4431559, 4467010, 4835062, 7328694, 7385077, 7415726, 8460938, 8689396, 9295594, 9661614. I used a computer for that!

fivemack · 2007-07-24, 08:36

Quote:

Originally Posted by Jens K Andersen

By the way, there are more congruent factorials modulo 71 than modulo any smaller prime. See http://primepuzzles.net/problems/prob_027.htm for more primes with many congruent factorials.
n! == 8978998 (mod 10428007), for n = 816488, 1251081, 3384225, 4112650, 4237275, 4431559, 4467010, 4835062, 7328694, 7385077, 7415726, 8460938, 8689396, 9295594, 9661614. I used a computer for that!

How did you do this - just compute the successive factorials modulo p and compute a histogram, or something cleverer with factorisations of differences of factorials? I suppose sum(p<N) p is about N^2/2 log N, which isn't that many small modular multiplies for N=10^7.

Jens K Andersen · 2007-07-24, 14:24

Quote:

Originally Posted by fivemack

How did you do this - just compute the successive factorials modulo p and compute a histogram ... I suppose sum(p<N) p is about N^2/2 log N, which isn't that many small modular multiplies for N=10^7.

Yes. http://primepuzzles.net/problems/prob_027.htm mentions my simple approach.

2007-07-20, 15:24	#1
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²·3³·19 Posts	Factorial To me this is a tricky one. I think its for people of Alpertron's and Maxal's calibre. Anyway its open for one and all! Show that 61! + 1 ==0 and 63! + 1 == 0 mod 71. Take a shot at it though. Mally Last fiddled with by mfgoode on 2007-07-20 at 15:34 Reason: wrong thread

2007-07-20, 20:26	#3
alpertron Aug 2002 Buenos Aires, Argentina 17·79 Posts	More verbose solution: According to Wilson's theorem (p-1)!+1 is divisible by p. Since 71 is prime, we have: 70!+1 = 0 (mod 71), which implies 70! = -1 (mod 71). Now 61! = 70!/(70696867...61) But 70 = -1, 69 = -2, 68 = -3, etc. (mod 71) so 70 69 * 68 ...62 = -9! (mod 71) (because the number of factors is odd). 61! = 70!/(-9!) -> 61! = 1/9! (mod 71) In the same way: 63! = 1/7! (mod 71) Now notice that 7! = 5040 = 71^2-1 = -1 (mod 71). So 63! = 1/(-1) = -1, then 63!+1 = 0 (mod 71) 9! = 987! = 727! = 17! = -1 (mod 71) So 61! = 1/(-1) = -1, then 61!+1 = 0 (mod 71) Last fiddled with by alpertron on 2007-07-20 at 20:37

2007-07-21, 15:42	#4
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²×3³×19 Posts	Right proof! Yeah wpolly and Alpertron thats about it! Good work, Thank you. Mally

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Multi-Factorial Search	rogue	And now for something completely different	1	2015-06-02 23:51
Factorial puzzle	henryzz	Puzzles	5	2015-04-02 12:58
Factorial primes	Unregistered	Information & Answers	2	2011-09-11 21:32
Factorial in C programming	Unregistered	Programming	7	2005-04-09 20:13
Factorial problem	xilman	Puzzles	12	2003-07-20 20:22

2007-07-20, 18:34	#2
wpolly Sep 2002 Vienna, Austria 3·73 Posts	61!=(9!)^(-1) (mod 71) 63!=(7!)^(-1) (mod 71) 7!=-1 (mod 71) 9!=72*7!=-1 (mod 71)

2007-07-23, 23:22	#5
Jens K Andersen Feb 2006 Denmark 2×5×23 Posts	By the way, there are more congruent factorials modulo 71 than modulo any smaller prime. See http://primepuzzles.net/problems/prob_027.htm for more primes with many congruent factorials. n! == 8978998 (mod 10428007), for n = 816488, 1251081, 3384225, 4112650, 4237275, 4431559, 4467010, 4835062, 7328694, 7385077, 7415726, 8460938, 8689396, 9295594, 9661614. I used a computer for that!