 mersenneforum.org Coset conundrum
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2021-08-28, 16:11 #1 Dr Sardonicus   Feb 2017 Nowhere 10111010110112 Posts 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 ri = remainder of k*b^(i-1) mod n [0 < ri < n], i = 1 to h. A) Prove that for a positive integer m. B) Prove that m = 1 if and only if n is a repunit to the base b, and also that one of the ri is equal to 1. Remark: The thread title refers to the fact that the ri form a coset of the multiplicative group generated by b (mod n) in the multiplicative group of invertible residues (mod n). Part (B) as I stated it above is completely wrong. I forgot to multiply a fraction by 1.  There is, alas, no connection to n being a repunit to the base b, or to any of the ri being 1, as shown by the example b = 10, k = 2, n = 4649 . Foul-up corrected in followup post. Last fiddled with by Dr Sardonicus on 2021-08-29 at 13:21 Reason: xingif stopy   2021-08-28, 21:28   #2
uau

Jan 2017

15010 Posts Quote:
 Originally Posted by Dr Sardonicus A) Prove that for a positive integer m.
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.
Quote:
 B) Prove that m = 1 if and only if n is a repunit to the base b, and also that one of the ri is equal to 1.
The "and also that one of the ri 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   2021-08-29, 13:26   #3
Dr Sardonicus

Feb 2017
Nowhere

3×1,993 Posts Quote:
 Originally Posted by uau The "and also that one of the ri 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
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.
(B) Let A = k*(bh - 1)/n, and sb(A) the sum of the base-b digits of A. Then m = sb(A)/(b-1).

Last fiddled with by Dr Sardonicus on 2021-08-29 at 13:29  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Dr Sardonicus Puzzles 3 2019-01-09 15:38

All times are UTC. The time now is 13:31.

Wed Sep 28 13:31:43 UTC 2022 up 41 days, 11 hrs, 0 users, load averages: 1.39, 1.37, 1.24

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔