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

If we say $n=p_1^{\alpha_1}\times p_2^{\alpha2}\times \cdots \times p_k^{\alpha_k}$, where $p_i$ are prime numbers, $\alpha_i$ are natural numbers, can or can we not say that:

Choose a $p_i$ such that it minimizes the quantity of $v_2(p_i-1)$.

1) Write $p_i=1+2^{\beta_i}\gamma_i$, where $\gamma_i$ is an odd integer, then $n\equiv 1 (\mbox{mod }2^{\beta_i})$ (I actually copied this out from a book. Just curious why is it true.)

Indeed, if the above is true, $n-1=2^{\beta_i}t$, for some integer $t$.

2) Is this true and why: $2^{2^{\beta_i}t}\equiv -1 (\mbox{mod }p_i)$

share|cite|improve this question
@ArturoMagidin I missed out some info just now. Now edited. Take a look please. Thanks. – yihangho Nov 28 '11 at 4:57
@ArturoMagidin Honestly, I am not very sure if it is possible. I am just reading a book by Titu Andreescu. So I assume everything in the book is true. Also, I typed wrongly on the second line. Should be $v_2(p_i-1)$ instead of $v_p$. – yihangho Nov 28 '11 at 5:16
@yihang: Well, what is in the book may very well all be true, but if what you type is not what is in the book, that makes a difference, doesn't it? – Arturo Magidin Nov 28 '11 at 5:26
@ArturoMagidin I get what you mean. Take a look at the extraction from the book below. – yihangho Nov 28 '11 at 6:09
Apologies guys. I misunderstood #2 and indeed what I typed here is wrong. But I have found a true solution to #1. – yihangho Nov 28 '11 at 23:59

Your assertion #1 can be restated as follows: if $\beta$ is chosen so that every prime dividing $n$ is congruent to 1 (mod $2^\beta$), then $n$ is congruent to 1 (mod $2^\beta$). Once you see that this is indeed a restatement, it should be clear why it's true: the product of a bunch of numbers that are 1 (mod $m$) is still 1 (mod $m$).

As far as I can tell, #2 is not true. $n=p$ could itself be a prime, in which case the left-hand side is $2^{p-1}$ which is congruent to 1, not -1, modulo $p$.

share|cite|improve this answer
I don't think $\beta$ can be chosen. – yihangho Nov 28 '11 at 5:42
It's a figure of speech; since $i$ is the one that minimizes $v_2(p_i-1)$, if all $p_j$ are congruent to $1$ modulo $4$, then $i$ is chosen with the smallest possible $\beta_i$; setting $\beta=\beta_i$ you get Greg Martin's observation. – Arturo Magidin Nov 28 '11 at 5:48
Oh now I get it. Thanks a lot. What about #2? The following is extracted directly from the book "Choose that $p_i$ which minimizes $v_2(p_i-1)$ and write $p_i=1+2^{\beta_i}\gamma_i$ with $\gamma_i$ odd. Then $n\equiv 1 (\mbox{mod } 2^{\beta_i})$ and we have $n-1=2^{\beta_i}t$. We have $2^{2^{\beta_i}t}\equiv-1 (\mbox{mod }p_i)$." – yihangho Nov 28 '11 at 6:08
Well, here we may assume that $n$ is not a prime. (Due to the requirement in the original problem.) – yihangho Nov 28 '11 at 6:37
#2 seems really very untrue to me. Take $n=21=3\times7$. No matter whether we take $p_i$ to be 3 or 7, we have $\beta_i = 1$ and $2^{\beta_i} t = 20$, but $2^20$ is not congruent to $-1$ modulo 3 or 7. – Greg Martin Nov 28 '11 at 23:49
up vote 0 down vote accepted

As I have commented on the questions and answer provided, assertion #2 is indeed invalid due to my misunderstanding. Apologies to everyone.

As for assertion #1, let us rearrange the $p_i$ such that $v_2(p_1-1)\le v_2(p_2-1)\le \cdots \le v_2(p_k-1)$

Now we can write $p_i=1+2^{\beta_i}\gamma_1$ for all $i\in\{1, 2, \cdots, k\}$ and we can see that $v_2(p_i-1)=\beta_i$. Hence, $\beta_1\le \beta_2\le\cdots\le \beta_k$. From this assumption, $p_i$ is the problem is actually $p_1$ here as it has the smallest value of $v_2(p_i-1)$

Notice that $p_i\equiv 1 (\mbox{mod }2^{\beta_1})$ for all $i\in\{1, 2, \cdots, k\}$. Take note that here the $p_i$ are congruent to $\beta_1$ not $\beta_i$ (although the congruence establish as well.) And hence, multiply up all the congruences, we get $n\equiv 1(\mbox{mod }2^{\beta_1})$.

share|cite|improve this answer
The main idea is same as @GregMartin but explained why $v_2$ is minimized. – yihangho Nov 29 '11 at 0:17

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.