chaotic_iak wrote: Determine all integer $n > 1$ such that \[gcd \left( n, \dfrac{n-m}{gcd(n,m)} \right) = 1\] for all integer $1 \le m < n$.

Round 2.5? BTW, use \gcd for gcd rather than just typing gcd. It makes it look nicer. Consider a prime power $p^k \| n$ where $p$ is the least prime divisor of $n$. Then remark that $p | \frac{n-m}{\gcd(n,m)}$ iff $v_p(n-m) > v_p(\gcd(n,m))$. This requires $p|m$, so let $v_p(m) = a$. If $a < k$ then $v_p(n-m) = v_p(\gcd(n,m)) = a$ and so $p$ does not divide the fraction in question. However, let $v_p(m) = k$ such that $v_p(n-m) \ge k+1$. This positive integer $m$ less than $n$ exists if $n$ is not a prime power of $p$, as otherwise just take $m/p^k \equiv n/p^k \pmod{p}$ and so $m < p^{k+1} < n$. But then $p | \frac{n-m}{\gcd(n,m)}$, contradiction as $\gcd (n, \frac{n-m}{\gcd(n,m)} ) \ge p$. When $n=p^k$ the problem obviously holds because $v_p(n-m) = v_p(m)$ and $v_p(\gcd(n,m)) = v_p(m)$ so the gcd is always $1$.

Otherwise known as "Long-Distance Training" where a set of problems is e-mailed every Friday to us and we submit our solutions by e-mail too. Yeah, I forgot that there is \gcd. Problem edited. My solution's sketch: - Suppose $n = dx, m = dy$ where $\gcd(x,y) = 1$; condition becomes $\gcd(dx, x-y) = 1$ - Note that $\gcd(d,x-y) = 1$ by above - If $n$ has more than one prime factor, there is some $y$ where $\gcd(x,y) = 1$ but $\gcd(d,x-y) > 1$ (to be precise, it's $d$); contradiction - If $n$ has exactly one prime factor, prove that it always satisfies the condition And done. The most natural solution that comes to mind, and hence perhaps quite long (although it only takes one page in Calibri 11pt ).