littletush wrote: Find all integers $k\ge 3$ with the following property: There exist integers $m,n$ such that $1<m<k$, $1<n<k$, $\gcd (m,k)=\gcd (n,k) =1$, and $k\mid (m-1)(n-1).$ Such that $1<m<k$, $1<n<k$, $\gcd (m,k)=\gcd (n,k) =1$, $m+n>k$ and $k\mid (m-1)(n-1).$ [mod: edited]

yunxiu wrote: littletush wrote: Find all integers $k\ge 3$ with the following property: There exist integers $m,n$ such that $1<m<k$, $1<n<k$, $\gcd (m,k)=\gcd (n,k) =1$, and $k\mid (m-1)(n-1).$ Such that $1<m<k$, $1<n<k$, $\gcd (m,k)=\gcd (n,k) =1$, $m+n>k$ and $k\mid (m-1)(n-1).$ My solution: If $k$ has primitive root then not satisfying And solutions otherwise. Prove that very easy!

A) If there exit a prime $p$, satisfy ${p^2}\left| k \right.$. We can take $m = n = \frac{{p - 1}}{p}k + 1$. B)If $k$ is square free. 1)$k$ has two prime factor $p > q \geqslant 3$. Let $a = \frac{k}{p}(p - 1) + 1$, $b = \frac{k}{p}(p - 2) + 1$, then $a = b + \frac{k}{p}$, as $\left( {\frac{k}{p},p} \right) = 1$, at least one of $a,b$ is corprime to $p$, we call it $m$, then $(m,k) = 1$, and $m > \frac{{p - 2}}{p}k \geqslant \left( {1 - \frac{2}{p}} \right)k$. Let $c = \frac{k}{q}(q - 1) + 1$, $d = \frac{k}{q}(q - 2) + 1$, then at least one of $c,d$ is corprime to $q$, we call it $n$, then $(n,k) = 1$, and $n > \frac{{q - 2}}{q}k \geqslant \left( {1 - \frac{2}{q}} \right)k$. Because $k\left| {(m - 1)(n - 1)} \right.$, if $m,n$ are not satisfy the codition, then $m + n \leqslant k$, hence$k \geqslant m + n > \left( {1 - \frac{2}{p}} \right)k + \left( {1 - \frac{2}{q}} \right)k$, so $\frac{2}{p} + \frac{2}{q} > 1$, the only solution is $p = 5,q = 3$, so $k = 3 \times 5 = 15$ or $k = 2 \times 3 \times 5 = 30$. If $k = 15$, we can take $m = 11$, $n = 7$. If $k = 30$, because $30\left| {(m - 1)(n - 1)} \right.$, we can suppose $5\left| {m - 1} \right.$, as $(m,30) = 1$, $m = 11$. So $3\left| {(n - 1)} \right.$， but $(n,30) = 1$, there is no solution. 2)If $k$ has not two prime factor $p > q \geqslant 3$. Then $k = p$ or $k = 2p, p \geqslant 3$, it is easy to see there are no such $m,n$. Above all, if an only if $k = 30$, $k$ is a prime or $k = 2p$, where $p$ is a odd prime, there are no such $m,n$.