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$ Commented Jul 18, 2022 at 0:14
  • $\begingroup$ @GerryMyerson Thanks, you are right. $\endgroup$
    – joro
    Commented 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
    Commented Jul 18, 2022 at 9:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .