0
$\begingroup$

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

  • 0
    A$p$ologies guys. I misunderstood #2 and indeed what I ty$p$ed here is wrong. But I have found a true solution to #$1$.2011-11-28

2 Answers 2

0

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

  • 0
    The main idea is same as @GregMartin but explained why $v_2$ is minimized.2011-11-29
2

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

  • 0
    @GregMartin You are right. #2 is really false due to my misunderstanding. Sorry.2011-11-28