mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Coset conundrum (https://www.mersenneforum.org/showthread.php?t=27106)

Dr Sardonicus 2021-08-28 16:11

Coset conundrum
 
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.

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.

uau 2021-08-28 21:28

[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

Dr Sardonicus 2021-08-29 13:26

[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.