Puzzle - RPL and others
05-10-2021, 05:13 PM
Post: #36
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
RE: Puzzle - RPL and others
I was a bit confused about proof of gcd(2n,d) buckets, perhaps this help.

Let base n = p*m, where p is power-of-2, m is odd, m > 1

d2p-1 * n + d2p ≡ 0 (mod 2p)
d2p ≡ (-p*m) * d2p-1 (mod 2p)
d2p / p ≡ -m * d2p-1 (mod 2) = 1 (mod 2)
d2p ≡ p (mod 2p) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿

→ d2p ≡ d4p ≡ d6p ≡ ... ≡ p (mod 2p)

dp-1 * n + dp ≡ 0 (mod p)
dp ≡ (-p*m) dp-1 = 0 (mod p)

→ d1p ≡ d3p ≡ d5p ≡ ... ≡ 0 (mod 2p) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ // p (mod 2p) were already taken

Instead of written in modulo form, we write the possible cases (we just don't know the order)
(note: m is odd, so m-1 is even, m-2 is odd ...)

d2p, d4p, d6p ... d(m-1)p﻿ ﻿ =﻿ ﻿ 1p, 3p, 5p ... (m-2)p
d1p, d3p, d5p ... d(m-2)p﻿ ﻿ =﻿ ﻿ 2p, 4p, 6p ... (m-1)p

Note indexes on the left does not match the possible values on the right.
But, if we swap the values (thru another indirection), both side matches.
Thus, we need to swap split buckets.

---

What happen if we extend this to gcd(4n, d) ?

d4p-1 * n + d4p ≡ 0 (mod 4p)
d4p ≡ (-p*m) * d4p-1 (mod 4p)
d4p / p ≡ -m * d4p-1 (mod 4) = ±1 (mod 4)
d4p / p ≡ 1 (mod 2)
d4p ≡ p (mod 2p)

Unfortunately, this is the same result from gcd(2n, d) buckets.
 « Next Oldest | Next Newest »

 Messages In This Thread Puzzle - RPL and others - Gene - 04-22-2021, 06:55 PM RE: Puzzle - RPL and others - Valentin Albillo - 04-22-2021, 11:52 PM RE: Puzzle - RPL and others - rprosperi - 04-23-2021, 04:21 PM RE: Puzzle - RPL and others - EdS2 - 04-23-2021, 07:30 AM RE: Puzzle - RPL and others - Dave Britten - 04-23-2021, 12:06 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:17 AM RE: Puzzle - RPL and others - ijabbott - 04-23-2021, 03:57 PM RE: Puzzle - RPL and others - Albert Chan - 04-23-2021, 04:08 PM RE: Puzzle - RPL and others - Albert Chan - 04-27-2021, 12:14 PM RE: Puzzle - RPL and others - Didier Lachieze - 04-23-2021, 04:23 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:05 PM RE: Puzzle - RPL and others - C.Ret - 04-24-2021, 04:40 PM RE: Puzzle - RPL and others - C.Ret - 04-25-2021, 09:25 AM RE: Puzzle - RPL and others - Claudio L. - 04-26-2021, 04:56 PM RE: Puzzle - RPL and others - 3298 - 04-27-2021, 08:16 PM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 02:33 AM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 03:30 AM RE: Puzzle - RPL and others - 3298 - 04-28-2021, 10:14 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 03:25 AM RE: Puzzle - RPL and others - Allen - 04-28-2021, 08:45 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 05:16 PM RE: Puzzle - RPL and others - Allen - 04-29-2021, 07:03 PM RE: Puzzle - RPL and others - C.Ret - 05-02-2021, 06:40 AM RE: Puzzle - RPL and others - 3298 - 05-03-2021, 03:43 PM RE: Puzzle - RPL and others - Albert Chan - 05-04-2021, 03:29 AM RE: Puzzle - RPL and others - 3298 - 05-04-2021, 06:48 AM RE: Puzzle - RPL and others - Albert Chan - 05-05-2021, 06:29 PM RE: Puzzle - RPL and others - 3298 - 05-06-2021, 04:24 PM RE: Puzzle - RPL and others - Albert Chan - 05-06-2021, 09:09 PM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 10:35 AM RE: Puzzle - RPL and others - 3298 - 05-07-2021, 04:17 PM RE: Puzzle - RPL and others - Albert Chan - 05-09-2021, 01:21 AM RE: Puzzle - RPL and others - 3298 - 05-09-2021, 01:39 PM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 03:57 AM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 02:56 AM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021 05:13 PM RE: Puzzle - RPL and others - 3298 - 05-10-2021, 08:23 PM RE: Puzzle - RPL and others - Albert Chan - 05-11-2021, 11:58 AM RE: Puzzle - RPL and others - 3298 - 05-11-2021, 02:14 PM RE: Puzzle - RPL and others - John Keith - 05-11-2021, 03:55 PM RE: Puzzle - RPL and others - ijabbott - 05-11-2021, 10:37 PM RE: Puzzle - RPL and others - Albert Chan - 05-13-2021, 11:38 PM

User(s) browsing this thread: 1 Guest(s)