We arranged all the prime numbers in the ascending order: $p_1=2<p_2<p_3<\cdots$. Also assume that $n_1<n_2<\cdots$ is a sequence of positive integers that for all $i=1,2,3,\cdots$ the equation $x^{n_i} \equiv 2 \pmod {p_i}$ has a solution for $x$. Is there always a number $x$ that satisfies all the equations? Proposed by Mahyar Sefidgaran , Yahya Motevasel
Problem
Source: Iranian TST 2017, first exam day 2, problem 4
Tags: number theory, Iran, Iranian TST, prime numbers, modular arithmetic
06.04.2017 20:16
06.04.2017 21:51
bgn wrote: We arranged all the prime numbers in the ascending order: $p_1=2<p_2<p_3<\cdots$. Also assume that $n_1<n_2<\cdots$ is a sequence of positive integers that for all $i=1,2,3,\cdots$ the equation $x^{n_i} \equiv 2 \pmod {p_i}$ has a solution for $x$. Is there always a number $x$ that satisfies all the equations? may be I miss understand the problem, but if we choose $n_i=p_i$ and $x=2$ , this $x$ satisfy the eqation for all $p_i$ , tell me if I make a mistake of lack understanding
06.04.2017 21:55
bgn wrote: Is there always a number $x$ that satisfies all the equations $?$
07.04.2017 00:04
An explicit counter example is to set $n_i=2p_i-3$ for all $i$. For odd primes $p$, the only solution to $x^{2p-3}\equiv2\pmod{p}$ is $x\equiv2^{-1}\pmod{p}$ by Fermat's Little Theorem. But it is clearly impossible for all odd primes to divide $2x-1$ for any integer $x$, so we are done. Note that this argument can strengthen the problem to infinirely many primes, not just all primes.
07.04.2017 00:40
Am I missing something or can you simply set $n_i = p_i-1$, so that $x^{n_i} \equiv 0,1 \pmod {p_i}$ i.e. there is no $x$? Thanks!
07.04.2017 00:58
MathPanda1 wrote: Am I missing something or can you simply set $n_i = p_i-1$, so that $x^{n_i} \equiv 0,1 \pmod {p_i}$ i.e. there is no $x$? Thanks! For every $x^{n_i}\equiv 2 \pmod {p_i}$ must be solution. Question is about existence common solution for all.
07.04.2017 01:27
Oh, I see what the problem means now! Thank you!
07.04.2017 05:47
This problem is pretty interesting
07.04.2017 05:54
It turn out that $x^a$-2 is that have infinity prime divisors with x is fixed and a turn to infinity ?
07.04.2017 06:23
Lam.DL.01 wrote: It turn out that $x^a$-2 is that have infinity prime divisors with x is fixed and a turn to infinity ? It is a case of Kobayashi's Theorem.
04.05.2017 07:32
$\textbf{My solution:}$ We can just let $n_i=\dfrac {p_i-1}{ord_{p_i}(2)}$, so the problem becomes proving no integer can be the primitive root of all prime numbers, this is just because every non-zero integer is the quadratic residue of infinite many prime numbers.
08.05.2017 21:14
Assume that we can always find such an $x$, and let $n_i=p_i+1000(p_i-1)$ for $i\geq 1000$: This implies $x\equiv 2\pmod{p_i}$ for all $i\geq 1000$, and hence $x=2$. But choosing $n_4=8$, gives the equation $x^8\equiv 2\pmod{7}\iff x^2\equiv 2\pmod{7}$, whose solutions are $x=3,4\pmod{7}$. We have a contradiction. $\blacksquare$ Why are we given that the $n_i$ are increasing? Looks like a useless condition to me.
11.02.2020 21:35
let $q_1<q_2.....$ be the primes that is congurent to $1 mod 8$ then $(\frac{2}{q_i})=1$ thus the equation $x^2 \equiv 2 mod q $ has a solution but it's impossible to have an $x$ that satisfies all of the equations unless we wil have $q_1q_2......|x^2-2$ put $q_1.q_2..... \longrightarrow \infty $ a contradiction
25.09.2022 01:07
No, let $n_i =p_i$ for $i \ne 4$ and let $n_4 =8$. For $p_i \ne 7$, we have $2^{p_{i}} \equiv 2$ (mod $p_i$) by FLT. For $p_i =7$, we have $3^{8} \equiv 3^{2} \equiv 2$ (mod $7$). Assume that we had a number $x$ satisfying all of the equations. If $q|x-1$ for some prime $q$, we would have $x^{q} \equiv 1$ (mod $q$), a contradiction. Thus, only $x=2$ is possible. However, we have $2^{n_{4}} \equiv 2^{8} \equiv 4$ (mod $7$) and so this cannot work either.
25.12.2024 16:30
sketch: