- **Puzzles**
(*https://www.mersenneforum.org/forumdisplay.php?f=18*)

- - **Coset conundrum**
(*https://www.mersenneforum.org/showthread.php?t=27106*)

Coset conundrumLet n > 2 be an integer, b an integer, 1 < b < n, gcd(b, n) = 1, gcd(b-1,n) = 1, and let h be the multiplicative order of b (mod n).
Let k be an integer, 1 <= k < n. Let r[sub]i[/sub] = remainder of k*b^(i-1) mod n [0 < r[sub]i[/sub] < n], i = 1 to h. A) Prove that [tex]\sum_{i=1}^{h}r_{i}\;=\;m\times n[/tex] for a positive integer m. [strike]B) Prove that m = 1 if and only if n is a repunit to the base b, and also that one of the[/strike] r[sub]i[/sub] [strike]is equal to 1.[/strike] Remark: The thread title refers to the fact that the r[sub]i[/sub] form a coset of the multiplicative group generated by b (mod n) in the multiplicative group of invertible residues (mod n). [b][color=red]Part (B) as I stated it above is completely wrong.[/color][/b] I forgot to multiply a fraction by 1. :gah: :blush: There is, alas, no connection to n being a repunit to the base b, or to any of the r[sub]i[/sub] being 1, as shown by the example b = 10, k = 2, n = 4649 . Foul-up corrected in followup post. |

[QUOTE=Dr Sardonicus;586729]
A) Prove that [tex]\sum_{i=1}^{h}r_{i}\;=\;m\times n[/tex] for a positive integer m. [/QUOTE] [SPOILER]If you multiply the elements of the set {b^i for all i} by b, you get the same set with permuted elements. Thus multiplying the sum by b does not change it mod n. Thus S*b = S mod n, S*(b-1)=0 mod n, and S must be 0 mod n.[/SPOILER] [QUOTE] B) Prove that m = 1 if and only if n is a repunit to the base b, and also that one of the r[sub]i[/sub] is equal to 1. [/QUOTE]The "and also that one of the r[sub]i[/sub] is equal to 1" part seems ambiguous or wrong. For k != 1, m may or may not equal 1? n = 1111, b = 10, k = 2: m = 1 n = 1111, b = 10, k = 21: m = 2 |

[QUOTE=uau;586757]<snip>
The "and also that one of the r[sub]i[/sub] is equal to 1" part seems ambiguous or wrong. For k != 1, m may or may not equal 1? n = 1111, b = 10, k = 2: m = 1 n = 1111, b = 10, k = 21: m = 2[/QUOTE] Mea culpa. I made a huge blunder. Actual characterization of the multiplier m follows, proof left as exercise. Conditions restated for ease of reference:[quote]Let n > 2 be an integer, b an integer, 1 < b < n, gcd(b, n) = 1, gcd(b-1,n) = 1, and let h be the multiplicative order of b (mod n). Let k be an integer, 1 <= k < n.[/quote] (B) Let A = k*(b[sup]h[/sup] - 1)/n, and s[sub]b[/sub](A) the sum of the base-b digits of A. Then m = s[sub]b[/sub](A)/(b-1). |

All times are UTC. The time now is 11:46. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.