I'm a complete beginner and not sure where to go with this proof of Euclid's lemma. Any help would be greatly appreciated.     If $m$ is a positive integer and a prime number $p$ is a factor of $m^2,$ then  $p$ is a factor of $m.$   So far I have:  Since we know that $m$ is a positive integer, then $m^2$ must also be positive. We also know that $p$ is positive integer, since it is a prime number.  So $m^2 = p*k$ where $k$ is positive since both $m^2$ and $p$ are positive. Therefore, $k$ is greater than or equal to $1.$  ...?
18057
The proof is already given in the textbook but I tried other way around.   Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,a)=1$ and $\gcd(p,b)=1$. Given that we can construct linear combinations   $sp+ta=1$ together with $up+wb=1$. Multiplying the left and the right sides of the equations we get  $spup+spwb+taup+tawb=1$ or $p(sup+swb+tau)+ab(tw)=1 \implies \gcd(p,ab)=1$. This is a contradiction.   Is it rigorous and sound proof?
94710
Given an integer $m=pq$, where $p,q$ are both primes such that $p\equiv 1 \pmod{4}, q\equiv 1 \pmod{4}$. It is known that $p$ can be written as a sum of two squares (of positive integers) in a unique way, and the same for $q$. Prove that $m$ can be written as a sum of two squares (of positive integers) in exactly two distinct ways.  Attempt  Notice that for positive integers $u,v,A,B$, we have \begin{align*}(u^2+v^2)(A^2+B^2)&amp;=(uA+vB)^2+(vA-uB)^2=(vA+uB)^2+(uA-vB)^2\end{align*} Therefore if $p=a^2+b^2,q=c^2+d^2$, then \begin{align*}m&amp;=(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(bc-ad)^2=(bc+ad)^2+(ac-bd)^2\end{align*} meaning that $m$ can be written as a sum of two squares (of positive integers) in at least two distinct ways.  How do I prove that there doesn't exist a third way of writing $m$ as a sum of two squares (of positive integers)?
75474
In Euclid's proof that there are infinitely many primes, the number  $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$.  Trivially, we could also use the number $R_n=p_1 p_2 ... p_n - 1$ to prove the theorem, for n>2.  Intuitively, as $n$ grows, the probability that $R_n$ is prime gets smaller. Is there a proof that $R_n$ is not prime for any $n$ greater than some integer $M$ ? Or conversely, that there is an infinite number of prime $R_n$ numbers?  A possibly equivalent question: Is there a prime number greater than $p_n$ and smaller than $R_n$ for any $n$ greater than some integer $M$ ?
44142
I'm not sure if this proof is valid or not and could use some feedback.  Let P be the supposition that $2^n \le 2^{n+1}-2^{n-1} - 1$ for all positive integers n.   Base Case: Let n=1  $2^1 \le 2^2-2^0-1$  $2\le2$   Suppose that P holds true for some positive integer n=k  $$2^{k+1}=2*2^k$$  By inductive hypothesis:  $$2*2^k \le 2(2^{k+1}-2^{k-1}-1)$$  $$2^{k+1} \le 2^{k+2}-2^{k}-2$$   Since we know $2^{k+1} \le 2^{k+2}-2^{k}-2$, we also know $2^{k+1} \le 2^{k+2}-2^{k}-1$ because the former is always smaller.  This proves that: $$2^k \le 2^{k+1}-2^{k-1} - 1\Rightarrow 2^{k+1} \le2^{k+2}-2^{k}-1 $$
85098
I need help!  I need to prove that for any $2 \le n,k$ positive integers $(n - 1)^2 \mid n^k -1$ if and only if $(n - 1) \mid k$  Thanks!
22704
Prove that $\gcd(2^{2^m}+1,2^{2^n}+1)=1$ if $m,n$ are positive integers.  Let $d=\gcd(2^{2^m}+1,2^{2^n}+1)$, then $d\mid 2^{2^m}+1$ and $d\mid2^{2^n}+1$ and then $d\mid2^{2^m}+1-2^{2^n}-1$, i.e. $d\mid2^{2^m}-2^{2^n}$ where we have taken $m&gt;n$. Thus $d\mid2^{2^n}(2^{2^{m-n}}-1)$, but $d \nmid 2^{2^n}$ thus $d\mid2^{2^{m-n}}-1$.  Then how will I proceed??
52765
I would like a proof that $$ {{n}\choose{k}} = \frac{n!}{k!(n-k)!} = 2^m $$ for $n,k,m\in \mathbb{N}$, only if $k=1$ or $k=n-1$.  It seems to me that this must be true since for other values of $k$ the numerator contains more factors that are not powers of 2 than the denominator. Furthermore, the numerator also contains larger factors than the denominator and thus can't all be cancelled. Nevertheless, I have been unable to form an elegant, watertight proof.
72907
Prove that for any even positive integer $n$, $n^2-1 \mid 2^{n!}-1$     This is from a book. They have given the proof. But I didn't understand it well. I am looking for a simpler proof. Or it will be helpful if someone explain this a little bit more - Proof: Let $m = n+1$ then we need to prove that $m(m-2) \mid 2^{(m-1)!}-1$. Because of $\phi(m) \mid (m-1)!$, we have $2^{\phi(m)} -1 \mid 2^{(m-1)!} -1$. And from Euler's theorem, $(m-2) \mid 2^{(m-1)!}-1$. Because $m$ is odd, $gcd(m,m-2)=1$ and the conclusion follows.
60543
I'm not entirely sure if I'm going about proving $n^2+n$ is even for all the natural numbers correctly.  $P(n): = n^2+n$     $P(1) = 1^2+1 = 2 = 0$ (mod $2$), true for $P(1)$   Inductive step for $P(n+1)$:     $\begin{align}P(n+1) &amp;=&amp; (n+1)^2+(n+1)\\ &amp;=&amp;n^2+2n+1+n+1\\ &amp;=&amp;n^2+n+2(n+1)\end{align}$   Does this prove $n^2+n$ is even as it's divisible by $2$? Thanks!
6868
Show that if the smallest prime factor $p$ of the positive integer $n$ exceeds $\sqrt[3]{n}$, then $\frac{n}{p}$ must be prime or 1.  I'm stuck trying to prove this. I tried this using contradiction, but I haven't been able to prove it.  My approach:  Let $p$ be the smallest prime factor of the positive integer $n$.  Let $p &gt; \sqrt[3]{n}$  Then we must show that $\frac{n}{p}$ is either a prime number or 1.  We know that $n = pe$ for some $e \in \mathbb{Z}$.  Thus, $\frac{n}{p} = e$  We also know that $p$ > $\sqrt[3]{n}$, so $p^3 &gt; n$, and $p^2 &gt; \frac{n}{p}$  So, assume $\frac{n}{p} = e$ is not prime nor 1, meaning it's a composite number. Let's try to get a contradiction.  If $\frac{n}{p}$ is composite, then $\exists a,b \neq 1: \frac{n}{p} = ab $  Now, here's where I get stuck. What can I do with this info? $\frac{n}{p} = ab $ and $p^2 &gt; \frac{n}{p}$.
117753
Prove that $$gcd(2^{2^m}+1, 2^{2^n}+1)=1$$ if $m, n$ are positive integers such that $m \neq n$.  A Hints to solve the problem is also given in the book as follows:  Let $m&gt;n$. Then $2^m=2^{n}2^{m-n}=2^n.2k$ for some integer $k$, (since $m&gt;n$). Let $2^{2^n}=x$. Then $2^{2^m}-1=x^{2k}-1$ and it is divisible by $x+1$.  I am still unable to solve. Please help.
37910
$m,n$ are integers bigger than 0.   I need to prove:  $$\frac{1}{\sqrt[n]{1+m}}+\frac{1}{\sqrt[m]{1+n}} \geq 1$$   I tried to multiply both sides by the common factor and raise both sides to the power of $m*n$ but it did not work for me, and I have no other idea how to proceed.  I don't want the full solution, but just a hint.  Thank you.
44758
Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z&lt;y$, then let $x=y/z$. Prove that $x$ must be a prime number.  Is there a simple way to solve this? It should be obvious but it's stumping me :/
4812
Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$  My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then we have that  $$ a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}} $$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$.   Beyond this, I am stuck at the moment.
63841
Prove or disprove: If $a \in \mathbb{Z}$, $a &gt; 0$, and $p$ is a prime such that $p^4 \mid a^3$, then $p^2 \mid a$.  I looked at the answers to the duplicate questions and I'm still confused. I can't even think of any counterexamples. Any tips on where to start?
73559
I have been reading about Pythagorean triples from the wiki page link .  It says that a pythagorean triple consists of 3 positive integer's $ a, b, c $ such that $ a^2 + b^2 = c^2 $.  Also if all the integers in a triple say $ a, b, c $ are relatively prime then the triplet is called Primitive Pythagorean triplet.  As I was reading more in this article it also described about generating  triple using Euclid's formula.  the formula is as follows :  $ a = m^2 - n^2, b = 2mn, c = m^2 + n^2 $ where $ m &gt; n &gt; 0 $  for any 2 values of $m$ and $n$ the above formula will give a Pythagorean Triple.  To get a Primitive Pythagorean triple, $m$ and $n$ have to co-prime and not both odd.  I wanted to understand the proof of this formula.  I don't understand this part of the proof which is also given in the wiki page.  "As ${{\tfrac {m}{n}}}$ is fully reduced, m and n are coprime, and they cannot both be even. If they were both odd, the numerator of ${\displaystyle {\tfrac {m^{2}-n^{2}}{2mn}}}$ would be a multiple of 4 (because an odd square is congruent to 1 modulo 4), and the denominator 2mn would not be a multiple of 4. Since 4 would be the minimum possible even factor in the numerator and 2 would be the maximum possible even factor in the denominator, this would imply a to be even despite defining it as odd. Thus one of m and n is odd and the other is even, and the numerators of the two fractions with denominator 2mn are odd. Thus these fractions are fully reduced (an odd prime dividing this denominator divides one of m and n but not the other; thus it does not divide m2 ± n2). One may thus equate numerators with numerators and denominators with denominators, giving Euclid's formula"
11582
Is my proof beneath perfect and complete?  I wanted to prove that for any nth root of an integer, if it's not an integer, than it's irrational: $$\begin{cases} m,n\in \mathbb{N}\\\sqrt[n]{m}\notin \mathbb{N} \end{cases}\implies \sqrt[n]{m}\notin \mathbb{Q}.$$  I start by assuming that $m^{\frac 1n}$ is rational and non-integer. So there exist  co-prime integers $a,b$ so that $$\sqrt[n]{m}=\frac{a}{b}$$ $$\implies  m=\frac{a^n}{b^n}\in\mathbb{N}.$$ But since $a$ and $b$ have no common factor, $a^n$ and $b^n$ also have no common factor. So: $$\frac{a^n}{b^n}\notin\mathbb{N},$$ a contradiction.