mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-07-20, 15:24   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Default 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
mfgoode is offline   Reply With Quote
Old 2007-07-20, 18:34   #2
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

21910 Posts
Default


61!=(9!)^(-1) (mod 71)
63!=(7!)^(-1) (mod 71)
7!=-1 (mod 71)
9!=72*7!=-1 (mod 71)
wpolly is offline   Reply With Quote
Old 2007-07-20, 20:26   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101010001002 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2007-07-21, 15:42   #4
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Thumbs up Right proof!



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

Mally
mfgoode is offline   Reply With Quote
Old 2007-07-23, 23:22   #5
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

E616 Posts
Default

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!
Jens K Andersen is offline   Reply With Quote
Old 2007-07-24, 08:36   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
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.
fivemack is offline   Reply With Quote
Old 2007-07-24, 14:24   #7
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

E616 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
Jens K Andersen is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.