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

80416 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

3·73 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

32×149 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 online now   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

2·5·23 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

6,379 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

2×5×23 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 12:47.

Fri Jan 22 12:47:57 UTC 2021 up 50 days, 8:59, 0 users, load averages: 2.32, 1.99, 1.75

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.