Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.


share|cite|improve this question
If $n = 8, d = 4$, then by the second condition $(8, t-1) = 8$, which implies $t - 1 \geq 8$. Thus $t \geq 9$. But you want a $t$ such that $1 \leq t \leq 8$ – Isomorphism Dec 17 '12 at 6:59
In this case we let t=1 and so (8,0)=8. – elham Dec 17 '12 at 7:08
up vote 3 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.