Demuestre que existen infinitos números primos$p$, tales que$\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

Question

Deje $a$, $b$ ser distintos números enteros positivos mayores que $1$. Demostrar que existen infinitos números primos $p$ tal que $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

(Aquí se $\mathrm{ord}_p(a)$ es el entero más pequeño $k>0$ tal que $a^k\equiv1\pmod p$.)

Este problema es desde el 2018 Iraní Olimpíadas de Matemáticas. No puedo encontrar ninguna fuente de la respuesta oficial. He intentado solucionarlo, pero no funcionó. Lo único que he encontrado es que si $p|\mathrm{gcd}(a-1,b-1)$, a continuación, $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)=1$.

Lo siento por la falta de información. Eso es todo lo que tengo que decir.

¿Cómo puedo solucionar el naranja problema? Si alguna de las fuentes de las que conoce, por favor, publicar las respuestas en la sección de respuestas aquí. Cualquier respuestas, soluciones o comentarios serán apreciados.

Si esta pregunta no se puede contestar, voy a borrar este post inmediatamente.

Answer 1

Una restricción : se supone que para algunos $p, v_p(a) > v_p(b)\ge 1$.

Deje $p_1,\ldots,p_j$ ser una lista de números primos que contienen los números primos dividiendo $a$. Deje $c > a+b$ e $N = \prod_{i=1}^j (p_i-1) p_i^c$. Para una potencia principal $q^r \equiv 1 \bmod N$si $p_i \nmid b$ entonces $b^{q^r}-a \equiv b-a {\scriptstyle\ \not \equiv \ 0}\bmod p_i^c$si $p_i | b$ entonces $b^{q^r}-a \equiv -a {\scriptstyle\ \not \equiv \ 0}\bmod p_i^c$.

Deje $h =\prod p_i^{v_{p_i}(\textstyle b^{q^r}-a)}= (\prod_{p_i | b} p_i^{v_{p_i}(a)}) (\prod_{p_i \nmid b} p_i^{v_{p_i}(b-a)} )$ $\scriptstyle(\text{note it doesn't depend on } q)$ y

$$\frac{b^{q^r}-a}{h} = \prod Q_l^{e_l} \qquad \qquad \scriptstyle (\text{which is coprime with } p_1\ldots p_j)$$

$b^{q^r}-a \equiv 0 \bmod Q_l, a \not \equiv 0 \bmod Q_l$ implica $\text{order}(a \bmod Q_l) \ |\ \text{order}(b \bmod Q_l)$.

Si también se $\gcd(q,Q_l-1) = 1$ entonces $\text{order}(a \bmod Q_l)= \text{order}(b \bmod Q_l)$.

Suponga $\forall l, \gcd(q,Q_l-1) \ne 1$, a continuación, $q | Q_l-1, Q_l = m_l q+1$ e $$\frac{b^{q^r}-a}{h} = \prod (m_lq+1)^{e_l} \equiv 1 \bmod q$$ Por lo tanto, es suficiente para elegir a $q \nmid b-a-h$, $q \nmid N, r = \phi(N)$ obtener $\frac{b^{q^r}-a}{h} \not \equiv 1 \bmod q$ así $Q_l | \frac{b^{q^r}-a}{h} $ tendremos $ \gcd(q,Q_l-1) = 1$ e $\text{order}(a \bmod Q_l)= \text{order}(b \bmod Q_l)$.

Agregar $Q_l$ a de la $p_i$ y repita el procedimiento para generar un número infinito de números primos tales que $\text{order}(a\bmod P)=\text{order}(b\bmod P)$.

La restricción $v_p(a) > v_p(b)\ge 1$ de inicio para asegurarse de $b-a-h \ne 0$.

Answer 2

Suponga que $b>a$. Deje $d=gcd(a,b)$, $x,y$ ser enteros positivos tales que $a=dx,b=dy$. Vamos a demostrar que existen infinitos números primos $p$ tal que $ord_p(a)=ord_p(b)$.

Definir $v_p(a)$ como el mayor entero tal que $p^{v_p(a)}|x$ pero $p^{v_p(a)+1}$ no divide $a$; $\phi(a)$ como el de Euler Totient función. Vamos a demostrar que el problema con dos pasos:

Paso 1: Hay al menos un primer $P$ tal que $ord_P(a) = ord_P(b)$ e $P$ no divide $a,b,b-a$.

En primer lugar, vamos a $t$ ser el mayor entero que divide $y$, de tal manera que todos los primos divisores de $t$ brecha $d$ (si $gcd(y,d)=1$, a continuación, elija $t=1$). Tendremos $gcd(\frac{y}{t},d)=1$ y por cada prime $p$ que divide $t$, $v_p(y)=v_p(t)$.

Con el teorema de Dirichlet sobre progresiones aritméticas podemos elegir una gran prime $Q$ tales que $$Q=(b-a)^2\phi(b-a)M+1,$$ with $M$ being an integer and: $$a^Q>b,Q>b+1, a^Q-b>t(b-a)>0, t|d^{Q-1}$$

A continuación, $$gcd(Q,a)=gcd(Q,b)=gcd(Q,b-a)=gcd(Q,d)=gcd(x,y)=gcd(x,y-x)=gcd(t,y-x)=1$$ y $$(b-a)|a^{Q}-a$$ since $$ a^{Q}-a =dx((a^{(b-a)^2\phi(b-a)M})^ {\phi(d(y-x))}-1) $$

Considerar el número de $a^Q-b$.

Tenga en cuenta que: $$a^Q-b=a^Q-a+a-b \equiv a-b \pmod Q$$ Entonces $$\frac{a^Q-b}{(b-a)} \equiv -1 \pmod Q$$

Vamos a demostrar que $\frac{a^Q-b}{t(b-a)}$ es solo divisible por los números primos que no se dividen $b-a$ e $d$, el uso de LTE teoremas:

Considerar los números primos $p$ que dividen $b-a$:

• Si $p$ divide $y-x$, a continuación, $p$ no divide $x,y$ y la: $$v_{p}(a^Q-a) = v_{p}(a^{\phi(b-a)M}-1)+2v_{p}(b-a)+v_{p}(a)>v_{p}(b-a)$$ if $p$ es impar.

  Si $p=2$ luego $$v_{2}((a^Q-a) = v_{2}(a^{\phi(b-a)M}-1)+v_{2}(a^{\phi(b-a)M}+1)+2v_{2}(b-a)-1+v_2(a) > v_{2}(b-a)$$ Thus $v_{p}(a^P-b)=v_{p}(b-a)$ for every prime $p$ that divides $y-x$.

• Si $p$ divide $d$ luego $$v_p(d^{Q-1}x^Q)>v_p(y)=v_p(t) \Rightarrow v_p(d^{Q-1}x^Q-y)=v_p(t) \Rightarrow v_p(dt)=v_p(a^Q-b)$$

Por lo tanto, $t|\frac{a^Q-b}{b-a}$ e $\frac{a^Q-b}{t(b-a)}$ es solo divisible por los números primos que no se dividen $b-a$ e $d$, y siempre existe el de los números primos, ya que $a^Q-b>t(b-a)$.

Vamos a demostrar que no existe algunos primos $P | \frac{a^Q-b}{t(b-a)}$ tal que $ord_P(a) = ord_P(b)$. Se puede ver que $P$ no divide $b-a, a, b$.

Deje $a^Q-b = \prod p_j^{\alpha_j}$ entonces $ord_{p_j}(b)=\frac{ord_{p_j}(a)}{gcd(ord_{p_j}(a),Q)}|ord_{p_j}(a)$ e si $\gcd(Q,p_j-1) = 1$ entonces $\gcd(Q,ord_{p_j}(a)) = 1$ lo $ord_{p_j}(a)=ord_{p_j}(b)$.

Si para todas las $j$, $gcd(Q,p_j-1) \ne 1$ entonces $Q | p_j-1$ lo $ \frac{a^Q-b}{t(b-a)} \equiv 1 \bmod Q$. Sin embargo $ \frac{a^Q-b}{b-a} \equiv \ -1 \bmod Q$ lo $ t \equiv \ -1 \bmod Q \Rightarrow Q|t+1$ una contradicción ya que el $Q>b+1$.

Por lo tanto, no existe algunos primos $P | a^Q-b$ tal que $ord_P(a) = ord_P(b)$ e $P$ no divide $b-a, a, b$.

Paso 2: Existen infinitos números primos $P$ tal que $ord_P(a) = ord_P(b)$ e $P$ no divide $b-a,a,b$.

Supongamos que hay finitely tales números primos $P_1,P_2,...P_k$. Con el teorema de Dirichlet sobre progresiones aritméticas podemos elegir una gran prime $Q$ tal que $Q=(b-a)^2\phi(b-a)\phi(P_1)\phi(P_2)...\phi(P_k)N+1$ con $N$ es un número entero y $a^Q>b$.

A continuación, $$a^Q-b \equiv a-b \neq 0 \pmod {P_i} \ \forall \ i \in {1,2,...,k}$$ A partir de aquí, se puede utilizar el mismo argumento desde el Paso 1 para demostrar que existe otra prime $P_{k+1}$ tal que $ord_{P_{k+1}}(a) = ord_{P_{k+1}}(b)$, $P_{k+1}$ no divide $b-a,a,b,d$ y diferentes a los de $P_1,P_2,...P_k$. Por lo tanto, debe haber un número infinito de números primos de satisfacer las condiciones.

A partir de los dos pasos podemos concluir que existen infinitos números primos $p$ tal que $ord_p(a) = ord_p(b)$

Los lemas utilizados en el post:

Para cada prime $p$, enteros $a$ tal que $p|a−1$, luego $$v_p(a^n−1)=v_p(a−1)+v_p(n)$$ if $p$ es impar, y $$v_2(a^n−1)=v_2(a−1)+v_2(a+1)+v_2(n)−1$$ for $p=2,2|n$.

Este es el corolario de la Elevación de La Exponente teorema, un conocido teorema. Usted puede ver aquí para pruebas.

Me tomó un largo tiempo para escribir todos estos, así que yo no haya sabido de ningún respuestas publicado que tenía las mismas ideas como la mía. Estoy muy triste por cualquier perturbación he hecho.

Cualquier comentario o modificaciones sugeridas será apreciado.

Answer 3

La PISTA.-Si $$a^k\equiv1\pmod p\\b^k\equiv1\pmod p$$ and you want to find some other prime $q$ such that $$a^l\equiv1\pmod q\\b^l\equiv1\pmod q$$ because of $a^l=a^k\veces a^{l-k}$, take for $n=1,2,3,\cdots$ the powers $a^{k+n}$ and $b^{k+n}$ , hasta que los números $a^{k+n}-1$ e $b^{k+n}-1$ no coprimes. (Tenga en cuenta que si siempre esta dos números son coprimes, a continuación, la proposición es falsa). Ejemplo: $$3^5\equiv1\pmod {11}\\4^5\equiv1\pmod {11}$$ and $$3^6=2^3\cdot7\cdot13+1\\4^6=3^2\cdot5\cdot7\cdot13+1$$ Thus you get two other examples whith $(3,4)$. Usted tiene $$3^6\equiv1\pmod q\\ 4^6\equiv1\pmod q$$ for the values $p=7$ and $13$.

Se debe tener claro que no siempre el nuevo primer aparecerá tan rápido.

Answer 4

Esta es una respuesta parcial solamente, mostrando que hay al menos un primer $p$ con $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

Elegir un primer $q$ lo suficientemente grande como para tener $ab\not\equiv 2\pmod q$. Como resultado,$(ab)^q-1\not\equiv 1\pmod q$, mostrando que no es el prime $p\mid (ab)^q-1$ con $p\not\equiv1\pmod q$; es decir, con $(q,p-1)=1$. En vista de $a^qb^q\equiv 1\pmod p$, esto implica $\mathrm{ord}_p(a)=\mathrm{ord}_p(b)$.

Mostrando que hay una infinidad de números primos $p$ con la propiedad en cuestión parece más complicado.

Answer 5

Deje $a = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{n}^{\alpha_{n}}$ e $b = q_{1}^{\beta_{1}} q_{2}^{\beta_{2}} \cdots q_{m}^{\beta_{m}}$ ser la factorización prima de $a$ e $b$. Definir $C$ el conjunto de los números primos que $ord_{p}(a) = ord_{p}(b) = 1$.

Deje $S = \{\ p_{1}, p_{2}, \ldots, p_{n}, q_{1}, q_{2}, \ldots, q_{m}\ \}$ e $\mathbb{P}$ el conjunto de los números primos. Tenga en cuenta que si $p$ es un número primo tal que $p \in (\mathbb{P} - S)$ , a continuación, por Fermat poco teorema $a^{p-1} \equiv 1 \pmod{p}$ e $b^{p -1} \equiv 1 \pmod{p}$, por lo tanto no es difícil mostrar que $ord_{p}(a) = ord_{p}(b) = 1$, yo. e., $p \in C$. Por lo tanto, $(\mathbb{P} - S) \subset C$.

Por último, tenga en cuenta que si $C$ es finito, a continuación, $(\mathbb{P} - S)$ es finito y por lo $\mathbb{P} = S \cup (\mathbb{P} - S)$ es finita, lo que contradice la del teorema de Euclides.