mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2018-01-29, 12:11   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

4408 Posts
Default 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!
lukerichards is offline   Reply With Quote
Old 2018-01-29, 13:16   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-01-29, 14:20   #3
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

22·3·5·29 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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?
Nick is offline   Reply With Quote
Old 2018-01-29, 14:22   #4
axn
 
axn's Avatar
 
Jun 2003

3×5×73 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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)?
axn is offline   Reply With Quote
Old 2018-01-29, 14:27   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

28810 Posts
Default

Quote:
Originally Posted by axn View Post
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
lukerichards is offline   Reply With Quote
Old 2018-01-29, 14:42   #6
axn
 
axn's Avatar
 
Jun 2003

3×5×73 Posts
Default

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
axn is offline   Reply With Quote
Old 2018-01-29, 14:50   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

1001000002 Posts
Default

Quote:
Originally Posted by axn View Post
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.
lukerichards is offline   Reply With Quote
Old 2018-01-29, 14:58   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

115538 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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?
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Observational Number Theory MattcAnderson Miscellaneous Math 8 2016-01-03 19:43
probabilistic number theory wildrabbitt Math 57 2015-09-17 18:26
Ask a number theory question wreck Math 4 2010-04-15 07:11
Easy number theory. mfgoode Puzzles 2 2006-05-30 09:46
number theory help math Homework Help 2 2004-05-02 18:09

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


Sun Oct 17 21:31:18 UTC 2021 up 86 days, 16 hrs, 0 users, load averages: 2.48, 2.01, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.