Clearly for all $p > 3$ we have $2| p - 1$ and $p - 1 > 2$. Therefore $\omega ( p - 1 ) \geq 2$. Let $q > 2$ be a prime such that $q|p - 1$. Suppose that $q|p! + 2^n$. Since $q \leq p - 1$ we have $q|p!$, hence $q| 2^n$. A contradiction. Therefore $p - 1$ and $p! + 2^n$ may possibly share in common only the prime $p = 2$. Therefore \begin{eqnarray*} \left. \left. \omega ( ( p - 1 ) \cdot ( p! + 2^n \right) \right) & = & 2 \end{eqnarray*} if and only if $q|p! + 2^n \Longrightarrow q \mbox { power of two}$. Therefore $\omega ( ( p - 1 ) \cdot ( p! + 2^n ) ) \geq 3$ if and only if \begin{eqnarray*} p! & = & 2^m - 2^n \end{eqnarray*} has no integer solutions in positive integers. We have \begin{eqnarray*} p! & = & \left. 2^n \cdot ( 2^{m - n} - 1 \right) \end{eqnarray*} Therefore $n = v_2 ( p! ) \leq p$. We have \begin{eqnarray*} 2^{m - n} & \equiv & 1 ( %Error. "tmop" is a bad command. {mod} p ) \end{eqnarray*} This implies that $m - n| \varphi ( p ) = p - 1$ or $p - 1| m - n$ (since $( 2, p ) = 1$) If $p - 1| m - n$ or $m - n = p - 1$ then \begin{eqnarray*} p^2 & | & 2^{m - n} - 1 \end{eqnarray*} And since $p! \equiv - p ( %Error. "tmop" is a bad command. {mod} p^2 )$ this implies that $p! = 2^n \cdot ( 2^{n - m} - 1 )$ cannot hold. Therefore $m - n|p - 1$ with $p - 1 \neq m - n$. Whence \begin{eqnarray*} m - n & \leq & \frac{p - 1}{2}\\ m & \leq & \frac{p - 1}{2} + n\\ & \leq & \frac{p - 1}{2} + p \end{eqnarray*} Therefore \begin{eqnarray*} p! & = & 2^m - 2^n\\ & \leq & 2^m\\ & \leq & 2^{\frac{p - 1}{2} + p} \end{eqnarray*} A contradiction.

{x} wrote: [...] Therefore $\omega ( p - 1 ) \geq 2$ [...] Why¿ (You need that $p-1$ is not a power of two). PS: $n!=2^a-2^b$ has only finetely many solutions, thus we could also check them

You are absolutely correct. Unfortunately by no means I can fix that today

Argh ! The "proof" is absolutely flawed. I leave you the pleasure of discovering the mistake

ZetaX wrote: PS: $n!=2^a-2^b$ has only finetely many solutions, thus we could also check them Hm, how can we do this? And why $n!=2^a-2^b$ has only finitely many solutions, I don't know?

The $2$ can be changed to any integer, see http://www.mathlinks.ro/Forum/viewtopic.php?t=55883 .

bilarev wrote: Let $p$ is such prime that $p^2$ divides $2^{p-1}-1$. Prove that for all positive integers $n$ the number $\left(p-1\right)\left(p!+2^n\right)$ has at least 3 different prime divisors. Here si my way to solve this problem. If $p$ has the form $2^k+1$then \[ 2^{p-1}-1=2^{{2^k}}-1=(2^{{2^{k-1}}}+1)(2^{{2^{k-2}}}+1)...(2+1) \] So $2^{p-1}-1$ can't dividisible by $p^2$. Now if ther existe such a $r$ that 1.$t<r$=>$2^t-1$ isn't div. by $p$ 2.$||2^r-1||_p=1$. then it is known that if $2^x-1|p^2$=>$x|rp$(it is not hard to prove) but as we have that $2^{p-1}-1|p^2$ and $(p-1;p)=1$=>there isn't such a $r$=> for any $q$ that $2^q-1|p$ we should have that $2^q-1|p^2$. Now if $p!+2^n=2^m$ then $2^n(2^{m-n}-1)|p$=>$2^{m-n}-1|p^2$ =>$2^{m-n}-1|p^2$=>$p!|p^2$=>$(p-1)!|p$ so we get to the contradiction.

I think you misunderstood something, Tiks, the problem says $p^{2}|2^{p-1}-1$, not the other way round.

Jumbler wrote: I think you misunderstood something, Tiks, the problem says $p^{2}|2^{p-1}-1$, not the other way round. Just read my solution again,leting that $X|Y$ means $X=kY$ for a positive integer $k$.

Hmm... I think there's still something strange. When you suppose there exists such a $r$, you have condition (1) as well, that is, if $t<r$ then $p$ doesn't divide $2^{t}-1$. But in your conclusion, you don't have this. I think it should be "for any $q$ that $p$ divides $2^{q}-1$ and $p$ doesn't divide $2^{t}-1$ when $t<q$, then $p^{2}$ divides $2^{q}-1$" Please correct me if I'm wrong

Jumbler wrote: Hmm... I think there's still something strange. When you suppose there exists such a $r$, you have condition (1) as well, that is, if $t<r$ then $p$ doesn't divide $2^{t}-1$. But in your conclusion, you don't have this. I think it should be "for any $q$ that $p$ divides $2^{q}-1$ and $p$ doesn't divide $2^{t}-1$ when $t<q$, then $p^{2}$ divides $2^{q}-1$" Please correct me if I'm wrong Look,let me restate my solution in other wards.I hope this time everything will be clear. At first I mentioned something like a lemma. Lemma.If $r$ is the smallest natural number such that $p|2^{r}-1$ and $p^{2}$ doesn't divide $2^{r}-1$,then any natural number $x$ that $p|2^{x}-1$ have the following form $x=kr$. Afterward I said that $p^{2}|2^{p-1}-1$ and $(p;p-1)=1$,which means that the set of numbers $r$ from the lemma is empty,that is for any natural number that $p|2^{r}-1$ we have that $p^{2}|2^{r}-1$. The last two lines of the solution are written rather clear . So,I hope now you haven't got any questions,have you?

Tiks wrote: So,I hope now you haven't got any questions,have you? No! It's a great solution

i agree with you, Tiks, regarding the fact that the order of $2$ in $\mathbb{Z}_{p}$ is the same with the order of $2$ in $\mathbb{Z}_{p^{2}}$. however, i don`t understand your proof. can you please explain it a little more ? my proof has somewhat similar ideas, but it is not exactly the same

maky wrote: i agree with you, Tiks, regarding the fact that the order of $2$ in $\mathbb{Z}_{p}$ is the same with the order of $2$ in $\mathbb{Z}_{p^{2}}$. however, i don`t understand your proof. can you please explain it a little more ? my proof has somewhat similar ideas, but it is not exactly the same Okay,let's proceed this way:you are telling me what exactly you don't understand in the proof(i.e. a statement,a formula and so forth), and I am trying to make it clear for you. Is that okay?

i don`t understand your proof that $r$ does not exist. more precisely, when you take $r$ the order of $2$ modulo $p$, and then you claim that if $2^{x}\equiv 1\pmod{p^{2}}$, then $x|rp$. i can`t understand this. what about $x=12345\cdot p(p-1)$ ?

maky wrote: i don`t understand your proof that $r$ does not exist. more precisely, when you take $r$ the order of $2$ modulo $p$, and then you claim that if $2^{x}\equiv 1\pmod{p^{2}}$, then $x|rp$. i can`t understand this. what about $x=12345\cdot p(p-1)$ ? Oh,I see the problem.But, actually I have asked you (Posted: Sun Nov 19,see above ) to understand by $X|Y$,that $X$ is dividisible by $Y$,see? So your conterexample does not work because $x=(12345(p-1))p$ is dividisible by $p$ ,and you should still define $r$ .

oh, sorry then. i have read now and i understood. i think i did the same thing... if $r$ is the order of $2$ modulo $p$, then $2^{pr}\equiv 1\pmod{p^{2}}$ and because $\gcd(p,p-1)=1$ it follows that $r$ is the order of $2$ modulo $p^{2}$.

We are already done if $p-1$ has at least $3$ different prime divisors. Therefore we need to consider $2$ other possibilities $p -1=2^aq^b$ or $p-1=2^a$, where $q$ is an odd prime and $a$ and $b$ are positive the integers. Consider the first case. Note that $q \mid p!$, meaning that $q$ does not divide $p!+2^n$. We are done if $p!+2^n$ is not a power of $2$. Therefore it remains to deal with the case, when for some positive integer $n$, the number $p!+2^n$ is equal to the power of $2$, say $2^m$. Then we have the following equation: $$ p!+2^n = 2^m \implies p! = 2^n(2^{m-n}-1) $$Observe that $p \mid 2^{m-n}-1 \implies 2^{m-n} \equiv 1 \pmod p$, but $p^2$ does not divide $2^{m-n}-1$. This means that $ord_p 2 \mid p-1$ and $ord_p 2 \mid m-n$. Assume that $ord_p 2 =d$. Then by LTE lemma, we have: $$ \nu_p(2^p -1) =\nu_p( (2^{d})^{\frac{p-1}{d}} -1) = \nu_p(2^d-1) + \nu_p(\frac{p-1}{d}) =\nu_p(2^d-1)+\nu_p(p-1) - \nu_p(d) = \nu_p(2^d-1) \ge 2$$This means that $2^d \equiv 1 \pmod {p^2} \implies (2^d)^{\frac{m-n}{d}} \equiv 2^{m-n} \equiv 1 \pmod {p^2}$ - contradiction. Now it remains to deal with the case when $p-1=2^a$. We will prove that it is impossible for the condition $p^2 \mid 2^{p-1}-1$ to be satisfied. Note that: $$ 2^{p-1}-1 =(2^{2^{a-1}}+1)(2^{2^{a-2}}+1) \ldots (2+1) $$ If we let $F_n =2^{2^{n}}+1$, then it is easy to prove that $F_n = F_0F_1 \ldots F_{n-1}+2$. This implies that $\gcd(F_i; F_j) =1$ for any $i \neq j$. Indeed suppose otherwise that there exists prime $p$ such that $p \mid F_i$ and $p \mid F_j$. WLOG assume that $i <j$. Then we $p \mid F_i \mid F_0F_1 \ldots F_j \implies p \mid 2$. But $F_n$ is an odd number - contradiction. This means that $2^{2^{a-1}}+1; 2^{2^{a-2}}+1, \ldots, 2+1$ are all pairwise coprime, which gives us that there exist $i$ such that $p^2 \mid 2^{2^{i}}+1$. On the other hand it is easy to show that if $p-1 =2^a$, then $a=2^c$ for some positive integer $c$. From before established results this means that $i=c$, but then $p^2$ obviously does not divide $2^{2^{i}}+1$. This exhausts all possible cases. Thus the problem is solved.