mersenneforum.org Factorial
 Register FAQ Search Today's Posts Mark Forums Read

 2007-07-20, 15:24 #1 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 22×33×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, 18:34 #2 wpolly     Sep 2002 Vienna, Austria 21910 Posts 61!=(9!)^(-1) (mod 71) 63!=(7!)^(-1) (mod 71) 7!=-1 (mod 71) 9!=72*7!=-1 (mod 71)
 2007-07-20, 20:26 #3 alpertron     Aug 2002 Buenos Aires, Argentina 101010001002 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!/(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) 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 22×33×19 Posts Right proof! Yeah wpolly and Alpertron thats about it! Good work, Thank you. Mally
 2007-07-23, 23:22 #5 Jens K Andersen     Feb 2006 Denmark E616 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!
2007-07-24, 08:36   #6
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

13×491 Posts

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.

2007-07-24, 14:24   #7
Jens K Andersen

Feb 2006
Denmark

E616 Posts

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
Yes. http://primepuzzles.net/problems/prob_027.htm mentions my simple approach.

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

All times are UTC. The time now is 06:46.

Sun Apr 18 06:46:32 UTC 2021 up 10 days, 1:27, 0 users, load averages: 1.63, 1.56, 1.67