As the title states, I'm supposed to prove for distinct primes $p_1,p_2 &gt;2$ the primes dividing $2^{p_1}-1$ and $2^{p_2}-1$ are distinct. The Wikipedia page on  states that #6: if $m$ and $n$ are natural numbers then $m$ and $n$ are coprime if and only if $2^m-1$ and $2^n-1$ are coprime, the only one without proof. I believe I have to prove the forward $(\Longrightarrow)$ direction.  edit: this was my own work for a homework question, and I was mainly wondering if the proof was okay. there is no proof directly provided on Wikipedia, and I didn’t find the links to the proof the clearest either. this was the clearest proof to me at the time and wanted someone else’s feedback because I couldn’t believe my proof was right.  My attempt at a proof (I use $a,b$ instead of $p_1,p_2$ or $m,n$): Suppose $(a,b)=1$ and $(2^a - 1, 2^b -1) = d$. Since $(a,b)=1$ there exist $x,y \in \mathbb{Z}$ s.t. $ax+by=1$. Since $a,b &gt; 2$, $x$ and $y$ cannot both be greater than zero, otherwise $ax+by &gt; 2+2 &gt;1$. Neither can $x$ or $y$ be equal to zero, otherwise $x$ or $y$ would $\not\in\mathbb{Z}$, or $ax+by=0\not=1$. Neither can $x$ and $y$ be less than zero, otherwise then $ax+by &lt;0&lt;1$. Thus one of $x$ or $y$ must be positive, while the other negative. Suppose $ax&gt;0$ then $by&lt;0$, then $d|2^{ax}-1$ and $d|2^{-by}-1$ since $$2^{ax}-1 = (2^a -1)((2^a)^{x-1}+(2^a)^{x-2}+\cdots+1)$$ $$2^{-by}-1 = (2^b -1)((2^b)^{-y-1}+(2^b)^{-y-2}+\cdots+1)$$ and $d|2^a -1$ and $d|2^b -1$ by definition. Then $2^{ax} - 1 = d\alpha$ and  $2^{-by} -1 = d\beta$ and then $2^{ax}-2^{-by} = 2^{-by}(2^{ax+by}-1)=2^{-by}(2^1-1)=2^{-by}  = d(\alpha -\beta)$ thus $d|2^{-by}$ and $d$ must be a power of $2$. But $d|2^a-1$ where $2^a-1$ is odd, and the only odd power of $2$ is $2^0=1$, hence $d=1$. If $(a,b)=1$ then $(2^a -1 ,2^b-1)=d=1$. Is my proof rigorous or am I missing something?
2481
For all $a, m, n \in \mathbb{Z}^+$,   $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
52713
The problem statement is: for $a,b$ coprime, prove that there exists positive integers $x,y$ such that $ax-by=1$.  The question is form Arthur Egnels' problem solving text, and from the chapter on the pigeonhole principle.    My question: His proof begins by generating a list $a,\ldots,a(b-1)$, where he then points out that each element in this list(which proceeds sequentially) doesn't have remainder $0\pmod{b}$.  He then shows that we arrive at a contradiction if we assume that we also don't get remainder $1$ in this list $\bmod b$.  To show the contradiction in this last statement, he first states that we would have positive integers $p,q $ where $ 0&lt;p&lt;q&lt;b$ so that $pa\equiv qa \pmod{b}$.  He then goes on to point out that since we $a$ and $b$ are coprime, we then have that $b| q-p$.  I understand the last part here, but don't see why we get $pa\equiv qa \pmod{b}$.  Thanks in advance
53347
Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.    I solve the problem in the following way: I assume that $m&gt;n$ then  $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.   But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.    Any idea?   Thanks!
51072
So I've been stuck on this proof for the past threes days now. I keep going back and forth and making no progress.     Let $n\in \mathbb{Z}_{\geq 2}$. Show that $\mathbb{Z}/n\mathbb{Z}$ has a nonzero nilpotent element iff there is a prime $p$ s.t. $p^2$ divides $n$.   $(\Rightarrow)$ I know $a$ can be factored into distinct primes, so $a=p_1^{e_1}\cdot ...\cdot p_m^{e_m}$ then $a^k=p_1^{e_1k}\cdot ...\cdot p_m^{e_mk}$.  Also since $n|a^k$ so $a^k=nd$ for some $d\in \mathbb{Z}$.  $a^k=p_1^{e_1k}\cdot ...\cdot p_m^{e_mk}=nd$. So $nd$ has that distinct prime factorization.  Then I get lost on what to do.
81671
I am trying to prove that not both integers $2^n-1,2^n+1$ can be prime for $n \not=2$. But I am not sure if my proof is correct or not:  Suppose both $2^n-1,2^n+1$ are prime, then $(2^n-1)(2^n+1)=4^n-1$ have 2 precisely two prim factors. Now $4^n-1=(4-1)(4^{n-1}+4^{n-2}+ \cdots +1)=3A$. So one of $2^n-1, 2^n+1$ must be 3. which implies $n=1$ or $n=2$ (rejected by assumption). Putting $n=1$, we have $2^n-1=1$ which is not a prime. Hence the result follows.  I also wanna know if there is alternative proof, thank you so much.
12941
The proof is a follows:  Let $p$ be a prime number and $x$ in Z. If $x^2\equiv1\pmod p$ then $x\equiv\pm1\pmod p$.  Proof: By assumption, $p | x^2 - 1 = (x + 1)(x - 1)$. Thus $p | x + 1$ or $p | x - 1$. This completes the proof.    However if $p | x + 1$ then $x$ is congruent to $-1 \mod p$. However why is $p$ congruent to $1 \mod p$ ??   I'm struggling seeing this, and been sitting for some hours now trying to figure it out - please help.
5562
Proof: The proof is by contradiction. Suppose there are only finitely many primes. Let the complete list be $p_1,p_2,\dots,p_n$. Let $N = p_1p_2 \dots p_n+1$. According to the Fundamental Theorem of Arithmetic, $N$ must be divisible by some prime. This must be one of the primes in our list. Say $p_k \mid N$. But $p_k\mid p_1\dots p_n$, so $p_k\mid(N-p_1 \dots p_n) = 1$ Hence contradiction.  I don't see how this proof works. I understand that $N$ isn't necessarily prime, but I don't understand how it apparently must show that some primes weren't in our list. A number could be made of different powers of the given primes right?  Someone please explain.
4426
Not sure if I'm doing this correctly but this is what I've done:  Assume that $n$ is composite and suppose $2^n-1$ is a prime for $n \gt 2$. Then, $2^n-1 = 2k$ for some $k \in \Bbb Z $, $\forall n$.  But this would be a contradiction since $n \gt 2$.  I'm not sure if this a correct proof.  EDIT: I realized that it's to prove $2^n - 1$ NOT $2^{n-1}$ so my attempt above is completely wrong.
111036
Prove that for any $m,n\in\mathbb{Z}^+$, the number $2^n-1$ is divisible by $(2^m-1)^2$ iff the number $n$ is divisible by $m(2^m-1)$.  My work so far:  It's an if and only if statement, so the common approach is to split the proof into two "if then" proofs ($A\rightarrow B \text{ and } B\rightarrow A$).  Starting with $A\rightarrow B$, for a direct proof, I would assume $A$ and prove $B$. I can use the definition of divisibility:  Assume $n=m(2^m-1)k$ for some integer $k$  Then I need to prove that $2^n-1=(2^m-1)^2h$ for some integer $h$  So I'm thinking I need to start with the expression $2^n-1$ and transform it to $(2^m-1)^2h$, or vice versa, and I need to use the assumption $n=m(2^m-1)k$ somehow.  I notice that the LS of the equality contains the variable $n$ while the RS contains $m$, and the assumption relates $n$ to $m$, so that could be a way forward. For example, simple substitution gives $2^{m(2^m-1)k}-1$, but I'm not sure what I could do from here. Perhaps there's a divisibility theorem that could help?  Other things I notice: $2^n-1$ and $(2^m-1)^2$ are always odd. Also, the divisors in both cases are multiples of $2^m-1$.  Any help/hints appreciated.
29905
I'm reading a proof in my number theory textbook that all primes of the form $p = 4k+1$ are uniquely the sum of two squares. I'm stuck right at the beginning of the proof, where they say:  To establish the assertion, suppose that $$ p = a^2 + b^2 = c^2 + d^2 $$ where $a,b,c,d$ are all positive integers. Then $$ a^2 d^2 - b^2 c^2 = p(d^2 - b^2). $$  Perhaps I'm just missing something obvious, but I can't figure out how they managed to conclude that $a^2 d^2 - b^2 c^2 = p(d^2 - b^2).$ Please advise.
12212
The question is     Suppose p is a prime number and p does not divide a. Prove that the congruence $ax \equiv 1 \mod p$ has a solution   (Without using Fermat's Theorem), I can intuitively tell this is true because since $p$ is prime, every $x &lt; p$ is co-prime to it, thus $$x \mod p$$  Will produce a unique integer for each $x \in \{0, 1, 2, .... p-1\}$, before it cycles over again at $p$. Clearly, some $x$ must have that $x \mod p = 1$. However, I don't know how to prove this for $ax$, mainly because I can't prove the ramifications it can have on the mod cycle. What I do know is that if for some $x$, we have: $$ax \equiv ay \mod p$$ Then since $p$ doesn't divide $a$ (by question assumption), it must divides $x - y$, implying that the solution for $ax \equiv 1 \mod p$ only depends on $x$, however, I don't know how to show this rigorously. Could anyone enlighten me?
39740
So today in my final for number theory I had to prove that the Fermat numbers ($F_n=2^{2^n}+1$) are coprime.   I know that the standard proof uses the following: $F_n=F_1\cdots F_{n-1}+2$ and then the $\gcd$ divides $2$, and it cannot be two, and hence the numbers are coprime.  However, he asked us to use the hint: "Let $l$ be a prime dividing $F_n$. What can you say about the order of $2$ in $(\mathbb{Z}/l\mathbb{Z})^\times$?"   I have been thinking about it and I cannot figure out how to use his hint.  Any ideas?
62954
I have just began learning number theory and I wanted to prove the following statement:   'if $x$ is coprime with each $p_i$ then $x$ is coprime with $p_1...p_n$'   This was actually a statement from a proof within CRT and they also had the condition that $p_i$ are pairwise coprime but I am not sure if that was used in proving the above statement.  Here is my attempt.  Suppose for a contradiction that $x$ is coprime with each $p_i$ and $x$ is not coprime with $p_1...p_n$, then there exists a prime number $q$ such that $q\mid x$, $q\mid p_1...p_n$. By the property that $q$ is prime we must have $q\mid p_i$ for some $i$. Hence $\operatorname{hcf}(x, p_i)\geq q$ for that specific $i$ and so there is a contradiction.   As I said, since I didn't use at all the pairwise coprime property of $p_i$, I am not sure if my proof was correct, could someone please let me know if there were any flaws in my argument?
105162
Suppose $n = pq$ with $p$ and $q$ distinct odd primes.   Suppose that $\gcd(a,pq)=1$. Prove that if the equation $x^{2} \equiv a\pmod n$ has any solutions, then it has four solutions.   Proof: Suppose $n = pq$ with $p$ and $q$ distinct odd primes and that gcd($a,pq$) = 1. Let us have the equation $x^{2} \equiv a\pmod n$. Then, $x^{2} \equiv a$ (mod $pq$), $p \not = q$. By definition, we can separate the equation into two equations such that $y^{2} \equiv a \equiv b$ (mod $p$) and $z^{2} \equiv a \equiv c$ (mod $q$). Let $g_{p}$ be a primitive root modulo $p$ and $g_{q}$ be a primitive root modulo $q$. Then, $b$ is equal to some power of $g_{p}$ and $c$ is equal to some power of $g_{q}$. With the fact that $b$ has a square root modulo $p$ (i.e. $r^{2} \equiv b$(mod $\ p)$) and $c$ has a square root modulo $q$ (i.e. $t^{2} \equiv c$(mod $\ q)$), there is an even power of $g_{p}$ and of $g_{q}$ such that $b = g_{p}^{2k_{1}}$(mod $\ p)$ and $c = g_{q}^{2k_{2}}$(mod $\ q)$ for some $k_{1}, k_{2} \in Z$. By computing, we have the following:  $r^{2} \equiv b$(mod $\ p)$       $\equiv b^{(p + 1) / 2}($mod $\ p)$       $\equiv (g_{p}^{2k_{1}})^{(p + 1) / 2}($mod $\ p)$       $\equiv (g_{p}^{p + 1})^{k_{1}}($mod $\ p)$       $\equiv g_{p}^{2k_{1} + (p - 1)k_{1}}($mod $\ p)$       $\equiv b \cdot g_{p}^{(p - 1)k_{1}}($mod $\ p)$       $\equiv b$ and $t^{2} \equiv c$(mod $\ q)$        $\equiv c^{(q + 1) / 2}($mod $\ q)$        $\equiv (g_{q}^{2k_{2}})^{(q + 1) / 2}($mod $\ q)$        $\equiv (g_{q}^{q + 1})^{k_{2}}($mod $\ q)$        $\equiv g_{q}^{2k_{2} + (q - 1)k_{2}}($mod $\ q)$        $\equiv c \cdot g_{q}^{(q - 1)k_{2}}($mod $\ q)$        $\equiv c$  Hence, $r$ is a square root of a modulo $p$ and $t$ is a square root of a modulo $q$, which means there are two solutions for each $p$ and $q$. Since $p \not = q \in \mathbb{Z}_{n}$, we have isomorphism such that $\mathbb{Z}_{n} \simeq \mathbb{Z}_{p} \cdot \mathbb{Z}_{q}$. Therefore, if the equation $x^{2} \equiv a$ (mod $n$) has any solutions, it must have four solutions. $\blacklozenge$  What do you think about the proof I wrote?
37176
Deduce that there is a prime gap of length $\geq n$ for all $n \in \mathbb{N}$   Show that if $2^n - 1$ is prime, then $n$ is prime.   Show that if $n$ is prime, then $2^n - 1$ is not divisible by $7$ for any $n &gt; 3$.       I'm not really sure how to do the first bit. For the second one, I'm not sure if this is correct but I have this: If $n$ is not prime, then $n = a b, a, b &gt; 1$. Also $2^n - 1 = (2 - 1)(1 + 2 + 2^2 + .... + 2^{n-1})$. So if we substitute for $n = ab$, we get $(2^a)^b - 1 = (2^a - 1)(1 + 2^a + (2^a)^2 + .... + (2^a)^{b - 1})$ which is now composite and so if $n = ab$, then $2^n - 1$. This means that $2^n - 1$ is prime if $n$ is prime. For the last one, we have a hint "Follow the example in lectures to show that $2^n - 1$ is not divisible by $3$", but I missed this lecture and haven't had a chance to get the note, so can someone help me with the divisible by $3$ bit and then I can try the divisible by $7$ bit myself.   Thank you  EDIT: I found a simpler proof for the second bit online:     Supposed $n$ is composite, it can be then written in the form $n = ab, a, b &gt; 1 \implies (2^a)^b - 1$ is prime with $b&gt;1$ and $2^a&gt;2$, contradicting statement $1$.   What is statement $1$? Maybe then I can understand why it contradicts it.
69724
The two primes $p$ and $q$ part of the public key need to be distinct. What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is there some other reason?
22623
I'd like to have my proof verified and if possible, to see other solutions that are interesting.  Proof: Suppose $n(n+1)$ is a square. Then we write $$n(n+1) = \prod_{p} p^{c(p)}$$ where $c(p) = a(p) + b(p)$ are such that \begin{align*} n &amp;= \prod_p p^{a(p)} \\ n+1 &amp;= \prod_p p^{b(p)} \end{align*} Now, by our hypothesis, $c(p)$ is even for all primes $p$. As $(n,n+1)=1$ for all $n$, it must be that $a(p)$ and $b(p)$ are even for all primes $p$ and moreover, $a(p) = 0$ whenever $b(p)&gt;0$ and reversely.  This indicates that both $n$ and $n+1$ are squares. This is impossible as there are no consecutive squares in the natural numbers.