PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Puzzle Of The Week

Author Message
Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95493 - Posted: 4 Jun 2016 | 21:00:54 UTC

Can you start a Puzzle or Problem Of The Week. Something from the range of High School to 1st year Grad level?

I'll start.

You are walking on a beach and you encounter a Genie. He says: If you can answer this question I will let you pass. Q: 1091 and 1647 are multiplicative inverses of each other in what base or modulo?

Profile DeleteNullProject donor
Volunteer tester
Avatar
Send message
Joined: 6 Apr 06
Posts: 262
ID: 2663
Credit: 11,771,362,904
RAC: 1,041,447
Discovered 68 mega primesEliminated 3 conjecture "k"sFound 4 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 2 mega primes in the 2019 Tour de PrimesFound 1 prime in the 2019 Tour de Primes Mountain StageFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 2 mega primes in the 2021 Tour de PrimesFound 2 primes in the 2022 Tour de PrimesFound 2 mega primes in the 2022 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (100,400,495)Cullen LLR Emerald: Earned 50,000,000 credits (67,814,375)ESP LLR Emerald: Earned 50,000,000 credits (73,880,409)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (66,597,607)PPS LLR Double Silver: Earned 200,000,000 credits (492,163,368)PSP LLR Double Bronze: Earned 100,000,000 credits (100,970,333)SoB LLR Double Bronze: Earned 100,000,000 credits (102,624,508)SR5 LLR Double Bronze: Earned 100,000,000 credits (114,278,918)SGS LLR Emerald: Earned 50,000,000 credits (54,295,707)TPS LLR (retired) Bronze: Earned 10,000 credits (61,785)TRP LLR Double Bronze: Earned 100,000,000 credits (102,088,428)Woodall LLR Emerald: Earned 50,000,000 credits (50,544,668)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (63,039,849)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,685,309)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (53,324,439)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (4,046,649,997)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,057,785)TRP Sieve (suspended) Emerald: Earned 50,000,000 credits (50,146,560)AP 26/27 Double Gold: Earned 500,000,000 credits (504,799,060)GFN Double Ruby: Earned 2,000,000,000 credits (2,929,260,403)WW Double Ruby: Earned 2,000,000,000 credits (2,546,832,000)PSA Double Silver: Earned 200,000,000 credits (226,683,337)
Message 95494 - Posted: 4 Jun 2016 | 22:05:46 UTC - in response to Message 95493.

211
____________
DeleteNull

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95498 - Posted: 4 Jun 2016 | 23:13:09 UTC - in response to Message 95494.

211


211 is incorrect

Maybe we should make it Problem Of The Month.

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95499 - Posted: 4 Jun 2016 | 23:15:01 UTC - in response to Message 95498.

211


211 is incorrect

Maybe we should make it Problem Of The Month.



Hint: the base or modulo must be greater than the larger of the two multiplicative inverses.

JimBProject donor
Honorary cruncher
Send message
Joined: 4 Aug 11
Posts: 918
ID: 107307
Credit: 977,945,376
RAC: 45
Discovered 1 mega prime321 LLR Ruby: Earned 2,000,000 credits (3,327,838)Cullen LLR Turquoise: Earned 5,000,000 credits (5,031,868)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,038,750)PPS LLR Turquoise: Earned 5,000,000 credits (5,000,461)PSP LLR Turquoise: Earned 5,000,000 credits (7,674,374)SoB LLR Sapphire: Earned 20,000,000 credits (42,604,648)SR5 LLR Jade: Earned 10,000,000 credits (11,829,173)SGS LLR Ruby: Earned 2,000,000 credits (2,537,053)TRP LLR Ruby: Earned 2,000,000 credits (2,291,092)Woodall LLR Turquoise: Earned 5,000,000 credits (5,046,412)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,057,614)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (52,042,965)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Emerald: Earned 50,000,000 credits (50,000,251)WW Ruby: Earned 2,000,000 credits (2,688,000)PSA Double Gold: Earned 500,000,000 credits (728,547,693)
Message 95501 - Posted: 4 Jun 2016 | 23:44:58 UTC - in response to Message 95493.

Q: 1091 and 1647 are multiplicative inverses of each other in what base or modulo?

It seems to me that modulo 2 they're both equal to 1 and 1 is the multiplicative inverse of itself.

Profile GrebulonerProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Nov 09
Posts: 450
ID: 49572
Credit: 2,417,108,605
RAC: 939,410
Discovered 3 mega primesFound 2 primes in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 3 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 7 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (29,930,364)Cullen LLR Sapphire: Earned 20,000,000 credits (20,754,874)ESP LLR Sapphire: Earned 20,000,000 credits (20,453,074)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (50,327,156)PPS LLR Emerald: Earned 50,000,000 credits (63,340,446)PSP LLR Sapphire: Earned 20,000,000 credits (20,571,669)SoB LLR Emerald: Earned 50,000,000 credits (50,873,282)SR5 LLR Sapphire: Earned 20,000,000 credits (23,807,284)SGS LLR Sapphire: Earned 20,000,000 credits (22,223,888)TRP LLR Sapphire: Earned 20,000,000 credits (20,191,201)Woodall LLR Sapphire: Earned 20,000,000 credits (20,376,385)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (55,630,889)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,178,073)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (56,046,594)PPS Sieve Double Gold: Earned 500,000,000 credits (521,014,891)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (9,468,384)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,076,645)AP 26/27 Double Gold: Earned 500,000,000 credits (511,802,405)GFN Double Silver: Earned 200,000,000 credits (278,220,852)WW Double Gold: Earned 500,000,000 credits (501,636,000)PSA Double Bronze: Earned 100,000,000 credits (126,200,096)
Message 95503 - Posted: 5 Jun 2016 | 1:09:09 UTC
Last modified: 5 Jun 2016 | 1:39:51 UTC

1091*1647 = 1 (mod 1796876) (I don't have the equivalence character handy)

Perhaps not the lowest modulo, but that wasn't the question :).

Edit: Okay, I "cheated" a little after finding the answer above and wrote a python program to brute force it and came up with 2129 as the lowest of 6 correct moduli. Referring to DeleteNull's answer of 211: (#4)449219=211*2129.
____________
Eating more cheese on Thursdays.

Profile DeleteNullProject donor
Volunteer tester
Avatar
Send message
Joined: 6 Apr 06
Posts: 262
ID: 2663
Credit: 11,771,362,904
RAC: 1,041,447
Discovered 68 mega primesEliminated 3 conjecture "k"sFound 4 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 2 mega primes in the 2019 Tour de PrimesFound 1 prime in the 2019 Tour de Primes Mountain StageFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 2 mega primes in the 2021 Tour de PrimesFound 2 primes in the 2022 Tour de PrimesFound 2 mega primes in the 2022 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (100,400,495)Cullen LLR Emerald: Earned 50,000,000 credits (67,814,375)ESP LLR Emerald: Earned 50,000,000 credits (73,880,409)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (66,597,607)PPS LLR Double Silver: Earned 200,000,000 credits (492,163,368)PSP LLR Double Bronze: Earned 100,000,000 credits (100,970,333)SoB LLR Double Bronze: Earned 100,000,000 credits (102,624,508)SR5 LLR Double Bronze: Earned 100,000,000 credits (114,278,918)SGS LLR Emerald: Earned 50,000,000 credits (54,295,707)TPS LLR (retired) Bronze: Earned 10,000 credits (61,785)TRP LLR Double Bronze: Earned 100,000,000 credits (102,088,428)Woodall LLR Emerald: Earned 50,000,000 credits (50,544,668)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (63,039,849)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,685,309)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (53,324,439)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (4,046,649,997)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,057,785)TRP Sieve (suspended) Emerald: Earned 50,000,000 credits (50,146,560)AP 26/27 Double Gold: Earned 500,000,000 credits (504,799,060)GFN Double Ruby: Earned 2,000,000,000 credits (2,929,260,403)WW Double Ruby: Earned 2,000,000,000 credits (2,546,832,000)PSA Double Silver: Earned 200,000,000 credits (226,683,337)
Message 95505 - Posted: 5 Jun 2016 | 5:46:10 UTC - in response to Message 95498.
Last modified: 5 Jun 2016 | 5:49:22 UTC

211


211 is incorrect

Maybe we should make it Problem Of The Month.


1091 = 36 (mod 211)
1647 = 170 (mod 211)
36 * 170 = 1 (mod 211)

2129 does it too.
____________
DeleteNull

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95511 - Posted: 5 Jun 2016 | 15:51:18 UTC - in response to Message 95505.

211


211 is incorrect

Maybe we should make it Problem Of The Month.


1091 = 36 (mod 211)
1647 = 170 (mod 211)
36 * 170 = 1 (mod 211)

2129 does it too.



2129 is the only correct answer.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1724
ID: 306875
Credit: 41,353,209
RAC: 13,572
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (593,283)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Jade: Earned 10,000,000 credits (16,511,963)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (4,228,147)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 95540 - Posted: 6 Jun 2016 | 8:35:40 UTC

In Z (the integers) we have:

1091*1647 = 1796877


So if n is the unknown modulus we seek, then:

1796877 == 1 (mod n)


This means that n can be any divisor of 1796877-1. We factorize:

1796876 = 2^2 * 211 * 2129


So we have the solutions:

n = 1, 2, 4, 211, 422, 844, 2129, 4258, 8516, 449219, 898438, 1796876.


If we require n to exceed 1647, then the solutions are 2129, 4258, 8516, 449219, 898438, 1796876. And if we required that and further that n is a prime, the only solution is 2129. However, as stated in the original post, all twelve n above are solutions.

/JeppeSN

Profile GrebulonerProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Nov 09
Posts: 450
ID: 49572
Credit: 2,417,108,605
RAC: 939,410
Discovered 3 mega primesFound 2 primes in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 3 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 7 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (29,930,364)Cullen LLR Sapphire: Earned 20,000,000 credits (20,754,874)ESP LLR Sapphire: Earned 20,000,000 credits (20,453,074)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (50,327,156)PPS LLR Emerald: Earned 50,000,000 credits (63,340,446)PSP LLR Sapphire: Earned 20,000,000 credits (20,571,669)SoB LLR Emerald: Earned 50,000,000 credits (50,873,282)SR5 LLR Sapphire: Earned 20,000,000 credits (23,807,284)SGS LLR Sapphire: Earned 20,000,000 credits (22,223,888)TRP LLR Sapphire: Earned 20,000,000 credits (20,191,201)Woodall LLR Sapphire: Earned 20,000,000 credits (20,376,385)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (55,630,889)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,178,073)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (56,046,594)PPS Sieve Double Gold: Earned 500,000,000 credits (521,014,891)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (9,468,384)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,076,645)AP 26/27 Double Gold: Earned 500,000,000 credits (511,802,405)GFN Double Silver: Earned 200,000,000 credits (278,220,852)WW Double Gold: Earned 500,000,000 credits (501,636,000)PSA Double Bronze: Earned 100,000,000 credits (126,200,096)
Message 95550 - Posted: 6 Jun 2016 | 15:10:20 UTC - in response to Message 95540.

In Z (the integers) we have:

1091*1647 = 1796877


So if n is the unknown modulus we seek, then:

1796877 == 1 (mod n)


This means that n can be any divisor of 1796877-1. We factorize:

1796876 = 2^2 * 211 * 2129


So we have the solutions:

n = 1, 2, 4, 211, 422, 844, 2129, 4258, 8516, 449219, 898438, 1796876.


If we require n to exceed 1647, then the solutions are 2129, 4258, 8516, 449219, 898438, 1796876. And if we required that and further that n is a prime, the only solution is 2129. However, as stated in the original post, all twelve n above are solutions.

/JeppeSN



I was wondering how to find the lower mods analytically, thank you. It's been 10+ years since my number theory class in college so I only had the basic workings in my head. Though I would argue, since we are talking about integers here, that n=1 should be excluded, as there is no 1 (mod 1).
____________
Eating more cheese on Thursdays.

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95552 - Posted: 6 Jun 2016 | 16:18:03 UTC - in response to Message 95540.

In Z (the integers) we have:

1091*1647 = 1796877


So if n is the unknown modulus we seek, then:

1796877 == 1 (mod n)


This means that n can be any divisor of 1796877-1. We factorize:

1796876 = 2^2 * 211 * 2129


So we have the solutions:

n = 1, 2, 4, 211, 422, 844, 2129, 4258, 8516, 449219, 898438, 1796876.


If we require n to exceed 1647, then the solutions are 2129, 4258, 8516, 449219, 898438, 1796876. And if we required that and further that n is a prime, the only solution is 2129. However, as stated in the original post, all twelve n above are solutions.

/JeppeSN



My apology, I should have stated or implied that the answer must be Prime.

Profile DeleteNullProject donor
Volunteer tester
Avatar
Send message
Joined: 6 Apr 06
Posts: 262
ID: 2663
Credit: 11,771,362,904
RAC: 1,041,447
Discovered 68 mega primesEliminated 3 conjecture "k"sFound 4 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 2 mega primes in the 2019 Tour de PrimesFound 1 prime in the 2019 Tour de Primes Mountain StageFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 2 mega primes in the 2021 Tour de PrimesFound 2 primes in the 2022 Tour de PrimesFound 2 mega primes in the 2022 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (100,400,495)Cullen LLR Emerald: Earned 50,000,000 credits (67,814,375)ESP LLR Emerald: Earned 50,000,000 credits (73,880,409)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (66,597,607)PPS LLR Double Silver: Earned 200,000,000 credits (492,163,368)PSP LLR Double Bronze: Earned 100,000,000 credits (100,970,333)SoB LLR Double Bronze: Earned 100,000,000 credits (102,624,508)SR5 LLR Double Bronze: Earned 100,000,000 credits (114,278,918)SGS LLR Emerald: Earned 50,000,000 credits (54,295,707)TPS LLR (retired) Bronze: Earned 10,000 credits (61,785)TRP LLR Double Bronze: Earned 100,000,000 credits (102,088,428)Woodall LLR Emerald: Earned 50,000,000 credits (50,544,668)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (63,039,849)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,685,309)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (53,324,439)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (4,046,649,997)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,057,785)TRP Sieve (suspended) Emerald: Earned 50,000,000 credits (50,146,560)AP 26/27 Double Gold: Earned 500,000,000 credits (504,799,060)GFN Double Ruby: Earned 2,000,000,000 credits (2,929,260,403)WW Double Ruby: Earned 2,000,000,000 credits (2,546,832,000)PSA Double Silver: Earned 200,000,000 credits (226,683,337)
Message 95555 - Posted: 6 Jun 2016 | 19:17:31 UTC

211 is prime.
____________
DeleteNull

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1724
ID: 306875
Credit: 41,353,209
RAC: 13,572
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (593,283)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Jade: Earned 10,000,000 credits (16,511,963)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (4,228,147)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 95556 - Posted: 6 Jun 2016 | 20:14:20 UTC - in response to Message 95555.
Last modified: 6 Jun 2016 | 20:21:05 UTC

211 is prime.


Yes. Of course it follows from my post above that the prime solutions are the prime factors of 2^2 * 211 * 2129, i.e. the primes 2, 211, and 2129. By the way, JimB gave the solution n=2 early (though not as early as you gave n=211). /JeppeSN

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1724
ID: 306875
Credit: 41,353,209
RAC: 13,572
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (593,283)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (112,799)PPS LLR Jade: Earned 10,000,000 credits (16,511,963)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (210,142)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (4,228,147)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 95557 - Posted: 6 Jun 2016 | 20:19:35 UTC - in response to Message 95550.

(...) Though I would argue, since we are talking about integers here, that n=1 should be excluded, as there is no 1 (mod 1).


The case n=1 gives the special ring {0} with one element which has some funny properties. In particular its only element 0 is a 1 because it works like a 1 on every element: 0*0=0. /JeppeSN

Profile GrebulonerProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Nov 09
Posts: 450
ID: 49572
Credit: 2,417,108,605
RAC: 939,410
Discovered 3 mega primesFound 2 primes in the 2018 Tour de PrimesFound 4 primes in the 2019 Tour de PrimesFound 3 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 7 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (29,930,364)Cullen LLR Sapphire: Earned 20,000,000 credits (20,754,874)ESP LLR Sapphire: Earned 20,000,000 credits (20,453,074)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (50,327,156)PPS LLR Emerald: Earned 50,000,000 credits (63,340,446)PSP LLR Sapphire: Earned 20,000,000 credits (20,571,669)SoB LLR Emerald: Earned 50,000,000 credits (50,873,282)SR5 LLR Sapphire: Earned 20,000,000 credits (23,807,284)SGS LLR Sapphire: Earned 20,000,000 credits (22,223,888)TRP LLR Sapphire: Earned 20,000,000 credits (20,191,201)Woodall LLR Sapphire: Earned 20,000,000 credits (20,376,385)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (55,630,889)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,178,073)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (56,046,594)PPS Sieve Double Gold: Earned 500,000,000 credits (521,014,891)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Turquoise: Earned 5,000,000 credits (9,468,384)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,076,645)AP 26/27 Double Gold: Earned 500,000,000 credits (511,802,405)GFN Double Silver: Earned 200,000,000 credits (278,220,852)WW Double Gold: Earned 500,000,000 credits (501,636,000)PSA Double Bronze: Earned 100,000,000 credits (126,200,096)
Message 95560 - Posted: 6 Jun 2016 | 20:39:30 UTC - in response to Message 95557.

Ah, the degenerate (of a sort) case, and most certainly the most trivial of all solutions. I went, perhaps, a little too literal in my thinking, then, that "1" (and thus modulo >1) had to at least be the result. I used to teach math and loved throwing degenerate figures at my geometry students just to see how they'd react and apply the theorems (that usually still worked, though we updated a few in the advanced class to make up for it).
____________
Eating more cheese on Thursdays.

Profile steveking
Send message
Joined: 22 May 16
Posts: 14
ID: 448042
Credit: 13,001,433
RAC: 0
PPS LLR Jade: Earned 10,000,000 credits (12,667,689)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (333,744)
Message 95567 - Posted: 7 Jun 2016 | 5:56:32 UTC - in response to Message 95555.

211 is prime.


Argh... prime and greater than the largest of the multiplicative inverse pair. Think Cryptography.

Profile composite
Volunteer tester
Send message
Joined: 16 Feb 10
Posts: 1022
ID: 55391
Credit: 887,943,190
RAC: 142,031
Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2022 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (6,055,323)Cullen LLR Gold: Earned 500,000 credits (776,297)ESP LLR Ruby: Earned 2,000,000 credits (3,433,680)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,443,837)PPS LLR Sapphire: Earned 20,000,000 credits (34,539,526)PSP LLR Turquoise: Earned 5,000,000 credits (6,587,988)SoB LLR Sapphire: Earned 20,000,000 credits (45,081,394)SR5 LLR Turquoise: Earned 5,000,000 credits (6,205,694)SGS LLR Ruby: Earned 2,000,000 credits (3,627,819)TRP LLR Turquoise: Earned 5,000,000 credits (7,078,152)Woodall LLR Amethyst: Earned 1,000,000 credits (1,693,614)321 Sieve (suspended) Emerald: Earned 50,000,000 credits (50,256,050)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,571,178)Generalized Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (50,009,610)PPS Sieve Double Silver: Earned 200,000,000 credits (463,452,443)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,165,888)TRP Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,071,454)AP 26/27 Turquoise: Earned 5,000,000 credits (6,798,063)GFN Emerald: Earned 50,000,000 credits (57,113,430)WW Ruby: Earned 2,000,000 credits (4,220,000)PSA Double Bronze: Earned 100,000,000 credits (102,762,384)
Message 96749 - Posted: 11 Jul 2016 | 8:13:32 UTC - in response to Message 95503.

1091*1647 = 1 (mod 1796876) (I don't have the equivalence character handy)

Perhaps not the lowest modulo, but that wasn't the question :).

Edit: Okay, I "cheated" a little after finding the answer above and wrote a python program to brute force it and came up with 2129 as the lowest of 6 correct moduli. Referring to DeleteNull's answer of 211: (#4)449219=211*2129.

I saw an interesting coincidence while verifying that 4 x 449219 = 1796876.

I meant to check 4 x 449219 = 1796876 But I typed 4 x 44219 = 176876

What immediately leaps out is that the third digit from the left (9) in the decimal notation for the number is squeezed out in both the LHS and RHS of the bottom version. I was curious to see why.

TLDR; It happens when the omitted digit is a 9 and the multipliers on the LHS produce a 9 in the product.
I leave it as a challenge to the interested reader to see if other digits can produce this effect.

Taking the difference of the two equations, we have
4 x (449219 - 44219) = 1796876 - 176876

whose value D is the 5-smooth number 1620000 with prime factorization: 2 2 2 2 2 3 3 3 3 5 5 5 5

We partition the factors of D for both the LHS and RHS of the difference of equations to understand what is happening.

Calling the squeezed digit M, in the Rth place (counting from 1) from the right end of D, M contributes M x 10 ^ (R - 1) to the total value of D.
This contribution is a multiple of (R - 1) 2s and 5s.

In the LHS the squeezed digit 9 is at R = 4, and in the RHS it is at R = 5.

For the RHS the squeezed digit's position accounts for the factors 2 2 2 2 5 5 5 5 of D.
The remaining factors are 2 3 3 3 3, which multiply to 162 = 179 - 17.
This expression generalizes as Q x 10 + M - Q = Q x 9 + M.
Since M is 9 we can rewrite this as 9 x (Q + 1).
Two of those remaining 3s are from the squeezed-out digit 9 and the remaining factors 2 3 3 are those of 17 + 1.
So that's the partitioning of the factors of the RHS.

On the LHS side R is 4, leaving the prime factors of 1620 = 4 x (449 - 44) as unrelated to the position of the digit M.
These factors are 2 2 3 3 3 3 5.
The multiplier 4 accounts for the two 2s, leaving 3 3 3 3 5 as the factors of 405 = 449 - 44 = 9 x (44 + 1).

Message boards : General discussion : Puzzle Of The Week

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.22, 0.42, 0.68
Generated 12 Aug 2022 | 8:44:21 UTC