Let $ p$ be a prime number and let $ a_1,a_2,\ldots,a_{p - 2}$ be positive integers such that $ p$ doesn't $ a_k$ or $ {a_k}^k - 1$ for any $ k$. Prove that the product of some of the $ a_i$'s is congruent to $ 2$ modulo $ p$.
Problem
Source:
Tags: induction, modular arithmetic, number theory unsolved, number theory
Umut Varolgunes
17.03.2008 07:46
I got some ideas about the problem.
Let $ w$ be a primitive root of $ p$. $ a_i=w^{k_i} (mod p)$ and $ a^s=2 (mod p)$. Hence the problem turns to this.
$ k_1,\ldots,k_{p-2}$ are positive integers such that $ p-1$ doesn't divide $ i.k_i$ for any $ i$. Prove that there are $ k_i$'s such that their sum is congruent to $ s$ modulo $ p$.
I think also this more general statement is true.
$ k_1,\ldots,k_{n-1}$ and $ n$ be positive integers such that $ n$ doesn't divide $ i.k_i$ for any $ i$. Prove that for every $ 0<r<n$ ($ r$ is a positive integer) there are $ k_i$'s such that their sum is congruent to $ r$ modulo $ n$.
Umut Varolgunes
22.03.2008 17:57
someone have an idea?
BaBaK Ghalebi
22.03.2008 18:24
a weird solution: we prove by induction on $ k = 2,\ldots , p - 1$ that there exists a set of integers $ \{b_{k,1},b_{k,2},\ldots ,b_{k,k}\}$ such that: (I)each $ b_{k,i}$ either equals $ 1$ or is the product of some terms of the sequence $ a_1,a_2,\ldots ,a_{p - 2}$. (II)$ b_{k,i}\not\equiv b_{k,j}\pmod p$ for $ 1\leq i < j\leq k$ suppose that we have chosen the set $ \{b_{k,1},b_{k,2},\ldots ,b_{k,k}\}$ for some integer $ 2\leq k\leq p - 2$. because $ a_k\not\equiv 0\pmod p$, no two of the numbers $ a_kb_{k,1},\ldots ,a_kb_{k,k}$ are congurent modulo $ p$. also,because $ a_k^k\not\equiv 1\pmod p$, we have: \begin{eqnarray*}\left(a_kb_{k,1}\right)\left(a_kb_{k,2}\right)\ldots\left(a_kb_{k,k}\right)\not\equiv b_{k,1}b_{k,2}\ldots b_{k,k}\pmod p\end{eqnarray*} hence, we cannot permute $ \left(a_kb_{k,1},\ldots ,a_kb_{k,k}\right)$ so that each term is congurent modulo $ p$ to the corresponding term in $ \left(b_{k,1},\ldots , b_{k,k}\right)$. because the $ a_kb_{k,i}$ are distinct modulo $ p$, there must exist $ j$ such that no two elements of the set $ \{b_{k,1},\ldots ,b_{k,k},a_kb_{k,j}\}$ are congurent modulo $ p$. we relabel this set of numbers as $ \{b_{k + 1,1},b_{k + 1,2},\ldots ,b_{k + 1,k + 1}\}$. each of these $ k + 1$ numbers equals $ 1$ or is the product of some terms of the sequence $ a_1,\ldots ,a_{p - 2}$, and the induction is complete. now consider the resulting list $ b_{p - 1,1},\ldots ,b_{p - 1,p - 1}$. exactly one of these numbers is congurent to $ 2$ modulo $ p$; because this number is not equal to $ 1$, it is congurent to the product of some of the $ a_k$, as desired.
Umut Varolgunes
22.03.2008 23:19
I think it is not weird BaBaK Ghalabi. Thanks for the solution.
RevolveWithMe101
16.08.2019 12:29
BaBaK Ghalebi wrote: a weird solution: we prove by induction on $ k = 2,\ldots , p - 1$ that there exists a set of integers $ \{b_{k,1},b_{k,2},\ldots ,b_{k,k}\}$ such that: (I)each $ b_{k,i}$ either equals $ 1$ or is the product of some terms of the sequence $ a_1,a_2,\ldots ,a_{p - 2}$. (II)$ b_{k,i}\not\equiv b_{k,j}\pmod p$ for $ 1\leq i < j\leq k$ suppose that we have chosen the set $ \{b_{k,1},b_{k,2},\ldots ,b_{k,k}\}$ for some integer $ 2\leq k\leq p - 2$. because $ a_k\not\equiv 0\pmod p$, no two of the numbers $ a_kb_{k,1},\ldots ,a_kb_{k,k}$ are congurent modulo $ p$. also,because $ a_k^k\not\equiv 1\pmod p$, we have: \begin{eqnarray*}\left(a_kb_{k,1}\right)\left(a_kb_{k,2}\right)\ldots\left(a_kb_{k,k}\right)\not\equiv b_{k,1}b_{k,2}\ldots b_{k,k}\pmod p\end{eqnarray*} hence, we cannot permute $ \left(a_kb_{k,1},\ldots ,a_kb_{k,k}\right)$ so that each term is congurent modulo $ p$ to the corresponding term in $ \left(b_{k,1},\ldots , b_{k,k}\right)$. because the $ a_kb_{k,i}$ are distinct modulo $ p$, there must exist $ j$ such that no two elements of the set $ \{b_{k,1},\ldots ,b_{k,k},a_kb_{k,j}\}$ are congurent modulo $ p$. we relabel this set of numbers as $ \{b_{k + 1,1},b_{k + 1,2},\ldots ,b_{k + 1,k + 1}\}$. each of these $ k + 1$ numbers equals $ 1$ or is the product of some terms of the sequence $ a_1,\ldots ,a_{p - 2}$, and the induction is complete. now consider the resulting list $ b_{p - 1,1},\ldots ,b_{p - 1,p - 1}$. exactly one of these numbers is congurent to $ 2$ modulo $ p$; because this number is not equal to $ 1$, it is congurent to the product of some of the $ a_k$, as desired. Can I ask what motivates this solution. Considering the sequence in that way is quite random I suppose