mersenneforum.org > Math Help with a number theory equivalence
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-29, 12:11 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25×32 Posts Help with a number theory equivalence Hi all, I've found a sequence of numbers which I have submitted to OEIS. Other contributors have taken an interest and found a simpler generating function to mine... ... except none of us know *why* it works. We don't want to include the function on the entry until we can explain why the simpler function outputs the same results. Essentially it comes down to this: Why is: $3^k+2\equiv0 \pmod {3^x+2}$ (k>x) equivalent to $3^k \equiv 1 \pmod {3^x+2}$ (k>x) The sequence was defined using the first equivalence, but a pari script, which works in a way equivalent to the second equivalence, generates the same numbers in a fraction of the time. But I'm not enough of a number theorist to ger my head around it!
2018-01-29, 13:16   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by lukerichards Hi all, I've found a sequence of numbers which I have submitted to OEIS. Other contributors have taken an interest and found a simpler generating function to mine... ... except none of us know *why* it works. We don't want to include the function on the entry until we can explain why the simpler function outputs the same results. Essentially it comes down to this: Why is: $3^k+2\equiv0 \pmod {3^x+2}$ (k>x) equivalent to $3^k \equiv -1 \pmod {3^x+2}$ (k>x) The sequence was defined using the first equivalence, but a pari script, which works in a way equivalent to the second equivalence, generates the same numbers in a fraction of the time. But I'm not enough of a number theorist to ger my head around it!
Edited the second one. To make more sense to me.

2018-01-29, 14:20   #3
Nick

Dec 2012
The Netherlands

1,759 Posts

Quote:
 Originally Posted by lukerichards Why is: $3^k+2\equiv0 \pmod {3^x+2}$ (k>x) equivalent to $3^k \equiv 1 \pmod {3^x+2}$ (k>x)
It's not entirely clear what you mean.
The conditions you have given relate to pairs of numbers k & x, and there exist positive integers k,x with k>x for which one condition holds and the other doesn't.
So how are you defining the sequence?

2018-01-29, 14:22   #4
axn

Jun 2003

5·29·37 Posts

Quote:
 Originally Posted by lukerichards The sequence was defined using the first equivalence, but a pari script, which works in a way equivalent to the second equivalence, generates the same numbers in a fraction of the time. But I'm not enough of a number theorist to ger my head around it!
I don't understand how this results in a sequence. Can you post both the original code that you used to generate, as well as the faster logic (along with the sequence itself)?

2018-01-29, 14:27   #5
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by axn I don't understand how this results in a sequence. Can you post both the original code that you used to generate, as well as the faster logic (along with the sequence itself)?
I'm happy to, although that wasn't exactly the question I had.

This doesn't result in a sequence - it is a part of calculating a sequence.

The entry on OEIS in draft (waiting for approval by an editor):

https://oeis.org/history/view?seq=A298827&v=34

 2018-01-29, 14:42 #6 axn     Jun 2003 5·29·37 Posts 3^k+2 == 3^x+2 (mod 3^x+2) 3^k == 3^x (mod 3^x+2) 3^(k-x) == 1 (mod 3^x+2) QED EDIT: In PARI, you would do znorder( Mod(3, 3^x+2)) Last fiddled with by axn on 2018-01-29 at 14:46
2018-01-29, 14:50   #7
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts

Quote:
 Originally Posted by axn 3^k+2 == 3^x+2 (mod 3^x+2) 3^k == 3^x (mod 3^x+2) 3^(k-x) == 1 (mod 3^x+2) QED EDIT: In PARI, you would do znorder( Mod(3, 3^x+2))
Thanks, that's really helpful.

And thank you for the patience you afforded me rather than just messaging me effectively saying "why don't you just learn some basic number theory?" and calling me an arrogant newbie.

2018-01-29, 14:58   #8
Dr Sardonicus

Feb 2017
Nowhere

32×643 Posts

Quote:
 Originally Posted by lukerichards Essentially it comes down to this: Why is: $3^k+2\equiv0 \pmod {3^x+2}$ (k>x) equivalent to $3^k \equiv 1 \pmod {3^x+2}$ (k>x)
Hmm. first congruence says 3^x + 2 divides 3^k + 2, which implies 3^x + 2 divides 3^k + 2 - (3^x + 2) = 3^k - 3^x. Since gcd(3^x, 3^x + 2) = 1, we have 3^x + 2 divides 3^(k-x) - 1.

The other congruence implies 3^x + 2 divides 3^k - 1. Does that help?

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Miscellaneous Math 8 2016-01-03 19:43 wildrabbitt Math 57 2015-09-17 18:26 wreck Math 4 2010-04-15 07:11 mfgoode Puzzles 2 2006-05-30 09:46 math Homework Help 2 2004-05-02 18:09

All times are UTC. The time now is 21:00.

Thu May 26 21:00:29 UTC 2022 up 42 days, 19:01, 1 user, load averages: 2.09, 1.85, 1.77

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.

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