Encontrar tal polinomio $f(x)\in \mathbb{Z}[x]$, que $$ \forall n\in \mathbb{N} \quad \gcd(f(n),f(2^n))=1$ $ este es un problema de la prueba de selección del equipo de indio. ¿Alguien me puede dar una solución a ella? Muchas gracias. Tengo no una sola idea sobre él.
Respuesta
¿Demasiados anuncios?
Esta prueba se obtiene por "trabajar hacia atrás" y escoger el más razonable de ruta que nos puede llevar a lo largo de la marcha atrás. Como soy campeón el enfoque de "trabajar desde la parte frontal y la parte de atrás y averiguar lo que el medio es" como una forma de resolver los problemas, déjame caminar a través de cómo se hace en este escenario. Hay mucho que aprender, así que tengan paciencia con este (muy largo) hacia atrás presentación. En particular, se muestra cómo generar ideas de lo que es dado, y la pieza para obtener una prueba.
Nota: Dado que se está trabajando en la India TST problemas, varios (menor de edad) de las piezas de este problema son de izquierda "para hacer". No debería afectar a la visión.
Vamos a utilizar los resultados bien conocidos, que
1) Para cualquier $ f \in \mathbb{Z} [x]$, $ a-b \mid f(a) - f(b)$.
2) de Fermat Poco Teorema (el Teorema de Euler)
Para hacer: Demostrar estos resultados.
Reclamo: Las únicas soluciones son $ f(x) = 1$$ f(x) = -1$. Claramente, estas funciones satisfacen las condiciones.
Miga de pan 1: queremos demostrar que las $ f( 2^n) = 1$ o $-1$ para todos los enteros $n$.
Para hacer: Mostrar que este fácilmente los resultados de la anterior afirmación.
Miga de pan 2: queremos demostrar que las $ f( 2^n) \mid f ( k)$ $ f(2^n) \mid f(2^k)$ algunos $k$.
Para hacer: Mostrar que este fácilmente los resultados de miga de pan 1.
(Senderismo / lado desvío de La ruta de exploración es innecesariamente fuerte, y que no podría ser capaz de demostrarlo. Vamos a soldado.
Miga de pan 3: (El único cuerdo camino que nos podría dar marcha atrás en) Vamos a clasificar (posible) los candidatos para $k$. Desde el 1 de conocido el resultado, $k = 2^n + Lf(2^n)$ donde $L$ es cualquier número entero, el trabajo.
Para hacer: Demostrar que esta familia de $k$ trabajo.
Ruta de 4: queremos demostrar que hay un $L$ tal que $ f(2^n) \mid f(2^{ 2^n + L f(2^n)})$. Para hacer: Demostrar que la ruta de 3 y 4 dan 2.
Ruta de 5: queremos demostrar que hay un $L$ tal que $ f(2^n) \mid 2^{ 2^n + L f(2^n)} -2^n = 2^n ( 2^{ Lf(2^n) + 2^n - n } -1)$.
Para hacer: Demostrar que la ruta de navegación de 5 da de ruta 4.
¿Cómo podemos mostrar esto? Tenemos poco control sobre nada. Esperar, Hace mostrando que el $ 2^{ L f( 2^n)} \equiv 2^{ n - 2^n} \pmod { f(2^n)}$ nos recuerdan algo? Así lo ve como Fermat Poco Teorema. Oh, qué diablos! Si sólo $f(2^n)$ fue un primer ...
Tales ilusiones. ¿Cómo podemos "hacer" es un primo? Bueno, si no es un número primo, vamos a tomar cualquier factor primordial $p$. Ahora, que dar marcha atrás nuestro pan rallado para solucionarlo. Recuerdo cuando me dijo que de miga de pan 2 es demasiado fuerte?
Miga de pan 2B: Para todos los $n$, para cualquier $ p \mid f(2^n)$, entonces existe un $k$ tal que $ p \mid f(k)$$ p \mid f(2^k)$.
Para hacer: Demostrar que también los resultados de miga de pan 1.
Miga de pan 3B: Vamos a clasificar (posible) los candidatos para $k$. Desde el 1 de conocido el resultado, $k = 2^n + Lp$ donde $L$ es cualquier número entero, el trabajo.
Para hacer: Mostrar que esta familia trabaja.
Miga de pan 4B: queremos demostrar que hay un $L$ tal que $ p \mid f(2^{ 2^n + L p})$.
Para hacer: Mostrar que 4B+3B implica 2B.
De ruta 5B: queremos demostrar que hay un $L$ tal que $ p \mid 2^{ 2^n + Lp} -2^n = 2^n ( 2^{ Lp + 2^n - n } -1)$.
Para hacer: Mostrar que el pan rallado 5B nos da 2B.
Ruta de 6B: Tome $ L = n - 2^n$. Si podemos aplicar de Fermat Poco Teorema, entonces estamos hecho, ya que el $ 2^{Lp} \equiv 2^{L} \equiv 2^{n - 2^n} \pmod{p}$.
Oh, espera, con el fin de aplicar de Fermat Poco Teorema, necesitamos $ p \neq 2$.
Para hacer : Tratar con el caso al $p=2$ ( $ 2 \mid f(2^n)$ ). Este es un one-liner.
Sugerencia: Muestre que $ 2 \mid f(2^{2^n} ) $.
Para hacer: Ahora que he caminado a través de cómo resolver esta prueba, escribir en el (mucho menor) hacia adelante de la forma.
Nota: no sé si miga de pan 2 es verdadera. Sospecho que hay escenarios donde no es, pero no me he molestado en investigar.
