mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-05-01, 04:50   #1
Trejack
 

23×251 Posts
Default Another "interesting" puzzle

I've come up with another "hard" puzzle I would like to share (and this is my second problem to come up with):

Are there a set of three primes a, b, and c such that:

(a*b) = 1 (mod c)
(a*c) = 1 (mod b)
(b*c) = 1 (mod a)

besides 2, 3, 5. I tried testing primes b, c with a = 2, and I could not complete the equation. Anyone else have an idea to this? Thanks.
  Reply With Quote
Old 2016-05-01, 10:12   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·733 Posts
Default

Nice puzzle. I'll give all solutions in (positive) integers.

We can assume that a<=b<=c. If a=1 then it is easy to see that b=1 and c can be anything. So (a=b=1,c) is a solution and its permutations.

Now, we can say that a>1, then from
a*b==1 mod c we get that c=(a*b-1)/k, where 0<k<a (otherwise c<b) and gcd(k,a*b)=1, because k|(a*b-1).
a*c==1 mod b is also true, so
a*(a*b-1)/k==1 mod b
a*(-1)/k==1 mod b
a+k==0 mod b
hence b|k+a, but 0<k+a<2*a<=2*b, so only b=k+a is possible.

Use the last equation:
b*c==1 mod a
(k+a)*(a*(k+a)-1)/k==1 mod a
k*(-1)/k==1 mod a
2==0 mod a, but a>1, so a=2, from this b=k+a, but 0<k<2, so k=1 and b=k+a=3, c=(a*b-1)/k=5.
(2,3,5) is really a solution, and there is no more.
R. Gerbicz is offline   Reply With Quote
Old 2016-05-05, 06:42   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

944710 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Nice puzzle. I'll give all solutions in (positive) integers.
Beautiful!
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Perpetual "interesting video" thread... Xyzzy Lounge 39 2021-03-12 14:19
Official "Interesting Animal Behavior" thread ewmayer Lounge 3 2016-05-30 15:26
"Interesting" post from the mailing list Dubslow Miscellaneous Math 13 2015-05-06 00:09
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 16:47.

Thu May 13 16:47:47 UTC 2021 up 35 days, 11:28, 1 user, load averages: 2.75, 2.56, 2.40

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.