Help with a number theory equivalence

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

(k>x)

equivalent to

(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!

[science_man_88]

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:

(k>x)

equivalent to

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

[Nick]

Originally Posted by lukerichards

Why is:

(k>x)

equivalent to

(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?

[axn]

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)?

[lukerichards]

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

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

[lukerichards]

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.

[Dr Sardonicus]

Originally Posted by lukerichards

Essentially it comes down to this:

Why is:

(k>x)

equivalent to

(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?