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$.
Problem
Source: 2012 Indonesia Round 2.5 TST 1 Problem 4
Tags: number theory, greatest common divisor, modular arithmetic, number theory proposed
10.05.2012 16:49
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$.
10.05.2012 17:45
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$.
11.05.2012 03:26
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 ).