Encuentra todos los enteros positivos $n$ s.t. $3^n + 5^n$ es divisible por $n^2 - 1$

Question

Como es la pregunta del título, estoy deseando encontrar todos los enteros positivos $n$ tal que $3^n + 5^n$ es divisible por $n^2 - 1$ .

Hasta ahora he demostrado que ambas expresiones son divisibles por $8$ para impar $n\ge 3$ por lo que trivialmente una solución es $n=3$ . Sin embargo, no estoy muy seguro de cómo proceder ahora. He conjeturado que la única solución es $n=3$ y han tratado de probarlo pero han tenido poca suerte. ¿Alguien puede indicarme la dirección correcta? gracias

Answer 1

EDITAR: como se ha señalado en los comentarios, esto no es correcto. Dejo la respuesta aquí por ahora por si alguien encuentra la forma de arreglarlo.

Por el pequeño teorema de Fermat, $a^n \equiv a \pmod{n}$ , siempre que $a$ y $n$ es coprima. Por lo tanto $$3^n + 5^n \equiv 8 \pmod{n+1}.$$ Pero esto debe ser congruente con $0$ desde $n^2-1=(n+1)(n-1)$ y por lo tanto también $n+1$ debe dividir la expresión y así $$8 \equiv 0 \pmod{n+1}.$$ Esto sólo ocurre cuando $n=1$ , $n=3$ o $n=7$ . Se puede comprobar el $n=7$ a mano, pero también podemos utilizar la congruencia para $n-1 = 6$ $$3^7 + 5^7 \equiv 3 + 5 \equiv 2 \not \equiv 0 \pmod{6}.$$

Answer 2

Esto no es una respuesta.

Hasta ahora conocemos los siguientes hechos:

1. El único $n\le 3\cdot 10^6$ para el que se cumple esta divisibilidad es $n=3$ . (Probado numéricamente.)

2. Está claro que 3 y 5 no se dividen $3^n+5^n$ y no es difícil demostrar que 7 y 11 tampoco se dividen $3^n+5^n$ .

3. Por lo tanto, si $n^2-1$ divide $3^n+5^n$ entonces 3,5,7,11 no se dividen $n^2-1$ . En particular, si $n^2-1$ divide $3^n+5^n$ , entonces 3 divide $n$ .

Answer 3

Esto me pareció un buen punto de partida para examinar la biblioteca GMP C con un poco más de detalle, así que decidí escribir un programa rápido para imprimir números que se ajusten a la descripción de este problema. No estoy seguro de que esto sea una "respuesta", pero pensé que el programa podría interesar a las partes interesadas.

Código abajo, enlace a un gist de github aquí .

// This program is a quick brute force test of the question described at
// http://math.stackexchange.com/questions/612346/find-all-positive-integers-n-s-t-3n-5n-is-divisible-by-n2-1

// Copyright (C) 2014 Victor Robertson

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

size_t gLower = 1;
size_t gUpper = (0 - 1); // force underflow = size_t max
size_t i;

void sig_handler(int signo)
{
    printf("tested %zu to %zu\n", gLower, i - 1);
    exit(0);
}

int main(int argc, char* argv[]) {

    // all n s.t. 3^n+5^n is divisible by n^2−1

    if (signal(SIGINT, sig_handler) == SIG_ERR) {
        return 1;
    }

    // set args if provided
    if (argc > 1) {
        gLower = atol(argv[1]);
        if (argc > 2) {
            gUpper = atol(argv[2]);
        }
    }

    i = gLower;

    mpz_t i_sqr, three_n, five_n, res;

    mpz_init(i_sqr);
    mpz_init(three_n);
    mpz_init(five_n);
    mpz_init(res);

    // start by calculating 3^n and 5^n where n is the first number to test
    mpz_ui_pow_ui(three_n, 3, i);
    mpz_ui_pow_ui(five_n, 5, i);

    // 3 is a known solution, might as well skip straight to 5
    if (gLower < 5) {
        printf("3\n");
        gLower = 5;
    }

    // adjust the lower bound to exclude odds
    if (gLower % 2 == 0) {
        gLower -= 1;
    }

    for(i = gLower; i < gUpper; i += 2) {
        // I think this can be accomplished in a better, possibly more efficient means though I'm not positive.
        mpz_ui_pow_ui(i_sqr, i, 2);
        mpz_sub_ui(i_sqr, i_sqr, 1);

        mpz_add(res, three_n, five_n);

        if (mpz_divisible_p(res, i_sqr)) {
            printf("%zu\n",i);
        }

        // multiple the current 3^n and 5^n by 3 and 5 respectively to acquire 3^(n+1) and 5^(n+1)
        mpz_mul_ui(three_n, three_n, 3);
        mpz_mul_ui(five_n, five_n, 5);
    }

    printf("Done!\n");

    mpz_clear(i_sqr);
    mpz_clear(three_n);
    mpz_clear(five_n);
    mpz_clear(res);
}

Answer 4

Desde $n$ es impar, tenemos $(3^n+5^n)\mid (3^{n^2}+5^{n^2})$ y por lo tanto $(n^2-1)\mid (3^{n^2}+5^{n^2})$ . En otras palabras, ambos $n$ y $n^2$ debe pertenecer al conjunto $$S=\{ m\in\mathbb{N} : (m-1)\mid (3^m+5^m)\},$$ que está representado por la secuencia http://oeis.org/A234535 en la OEIS.

Por lo tanto, es interesante considerar una cuestión (posiblemente más simple) de encontrar todos los cuadrados en $S$ .