2012 China TST Quiz3-Day2-2(BOMC-2)

[Tahmid Hasan]

Find all integers $k \geq 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)$

[Phlembac Adib Hasan]

Solution :

First we'll claim that we can take all the natural numbers as $k$ excluding all the non-composite numbers and all the integers of the form $2q$ where $q$ is an odd prime.
Before going through the general case, let's consider some special cases.
The conditions $1<m<k$ and $1<n<k$ imply together that none of $m-1$ and $n-1$ is co-prime with $k$ because $k|(m-1)(n-1)$.So we can't take any prime as $k$ because all the smaller numbers are co-primes with it.But we can take any prime power as $k$ because both $p^{a-b}+1$ and $p^b+1$ are co-primes with $p^a$ and $p^a|p^{a-b}p^b=p^a$ for any prime $p$,$a>1$ and $1\leq b<a$.
Now let $k=2q$ where $q$ is an odd prime.There exists only one multiple of $q$ between $1$ and $2q$ which is $q$.But $q+1$ is even which is not co-prime with $2q$.So we can't take $2q$ as $k$.
Now we'll start the general case.
Let $k=\prod_{i=1}^r p_i^{\alpha _i}$ with $p_i=\text {prime}$.If some $\alpha _c,\alpha _d,...,\alpha _x$ are greater than one, then take $m=n=p_1^{\alpha _1}p_2^{\alpha _2}...p_c^{\alpha _c-1}...p_d^{\alpha _d-1}...p_r^{\alpha _r}+1$.So we can take all the integers as $k$ which has at least one $\alpha_i>1$.
Now, one case is left : to check out where $\alpha _1=\alpha _2=...=\alpha _r=1$.
\[\therefore k=p_1p_2...p_r\]\[\Rightarrow k=\left (p_1p_2...p_{r-1}\right )p_r\]I'll define two series as $w_i=i\left (p_1p_2...p_{r-1}\right )+1$,$1\leq i\leq p_r$ and $v_i=ip_r+1$,$1\leq i\leq p_1p_2...p_{r-1}$.
Notice that all the $w_i$s makes a complete residue set modulo $p_r$.So there is only one $j$ for which $w_j$ is dividable by $p_r$.So take any of the $w_i$s (excluding $w_j$) as $m$.Similarly choose $n$ from $v_i$s.(But notice that $p_1p_2...p_{r-1}$ is a composite number.So at first you have to find out the reduced residue set from $v_i$s(complete residue set) and then you can take any element from this set as $n$)
Notice that this proof breaks down if $p_r=2$.But we have proved $k\neq 2q$ at the first.So there is at least two odd primes in $k$.Then write $k$ like this $(2f)p_r$ where $p_r$ is an odd prime, and $f$ is the product of the rest odd primes.Now continue like the previous to complete the proof.