# Questions regarding congruences of multiples and relatively prime numbers

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

• @ArturoMagidin I missed out some info just now. Now edited. Take a look please. Thanks. Nov 28, 2011 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$. Nov 28, 2011 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? Nov 28, 2011 at 5:26
• @ArturoMagidin I get what you mean. Take a look at the extraction from the book below. Nov 28, 2011 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. Nov 28, 2011 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$.

• I don't think $\beta$ can be chosen. Nov 28, 2011 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. Nov 28, 2011 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)$." Nov 28, 2011 at 6:08
• Well, here we may assume that $n$ is not a prime. (Due to the requirement in the original problem.) Nov 28, 2011 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. Nov 28, 2011 at 23:49

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

• The main idea is same as @GregMartin but explained why $v_2$ is minimized. Nov 29, 2011 at 0:17