4
$\begingroup$

Let n be an even number and d be divisor of n/2. Then prove there is a number $1\leq t\leq n$ such that $(t,n)=1$ and $(n,t-1)=2d$.

$(n,t)$ is the common largest divisor of n , t. Also let $(n,0)=n$.

Thanks.

  • 1
    In this case we let t=1 and so (8,0)=8.2012-12-17

1 Answers 1

3

The condition on $d$ is equivalent to requiring that $2d$ is an even divisor of $n$. In fact we can prove the statement for a divisor $r$ of $n$ under the weaker hypothesis that either $n$ is odd or $r$ is even.

Let $n=p_1^{n_1}\cdots p_k^{n_k}$ and $r=p_1^{r_1}\cdots p_k^{r_k}$ with $r_i\le n_i$. By the chinese remainder theorem, there is $t$ such that $t\equiv p_i^{r_i}+1\bmod p_i^{n_i}$ for all $i$. Then $t$ is not divisible by any of the odd prime factors of $n$. If $n$ is odd, all its prime factors are odd. If $r$ is even, $t$ is not divisible by $2$. In either case, $t$ is not divisible by any of the prime factors of $n$, so $(t,n)=1$. On the other hand, $t-1\equiv p_i^{r_i}\bmod p_i^{n_i}$ for all $i$, so $(n,t-1)=r$.