1
$\begingroup$

For natural $n$, define the sequence

$$ a(n)=\gcd(2^n-1,\phi(2^n-1)) $$

It doesn't appear to be in OEIS and starts $1,1,1,1,9,1,1,1,3,1,9,1,3,1,1,1,27,1,75,49$

Q1 Can we unconditionally prove $a(n)=1$ infinitely often?

(Infinitely many Mersenne primes $M_p$ implies it).

Q2 Can we unconditionally prove $a(n)$ is bounded infinitely often?

Q3 Can we unconditionally prove $a(n)$ is unbounded infinitely often?

Q4 In case $a(n)$ is unbounded infinitely often, is its factorization related to named prime numbers?

Experimental investigation is not very tractable because of expensive factorization.

$\endgroup$
2
  • 1
    $\begingroup$ "unbounded infinitely often" is just "unbounded". $\endgroup$ Jul 18, 2022 at 0:14
  • $\begingroup$ @GerryMyerson Thanks, you are right. $\endgroup$
    – joro
    Jul 18, 2022 at 9:16

1 Answer 1

7
$\begingroup$

Q3: certainly yes. Take $n=2\cdot 3^{k}$, then $2^n-1$ is divisible by $3^{k+1}$,thus $3^k$ divides $a(n)$.

As for Q1 and Q2, I do not see how to avoid the scenario when $2^n-1$ is always divisible by a square of a prime.

$\endgroup$
1
  • $\begingroup$ Thanks, you have sharp eye about divisibility and recognizing square factors. $\endgroup$
    – joro
    Jul 18, 2022 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.