mersenneforum.org > Math Help with a number theory equivalence
 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
Dartmouth NS

2×52×132 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

111001010102 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

10101010101002 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

12016 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 22·3·5·7·13 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

25·32 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))

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

24·3·7·19 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 23:09.

Fri Jun 2 23:09:55 UTC 2023 up 288 days, 20:38, 0 users, load averages: 0.82, 1.09, 1.07