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

-
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

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. –  yihangho Nov 29 '11 at 0:17