4
votes
1answer
65 views

For $n\ge4$, prove that $1!+2!+\cdots+n!$ cannot be the square of a positive integer

I'm trying to prove this by induction but seem to be getting nowhere.
3
votes
6answers
71 views

Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$ for any two integers $a$ and $b$? Intuitively it is true because when you divide $a$ and $b$ by ...
1
vote
0answers
57 views

Proof Synopsis of Fermat's Last Theorem

I'm taking a introduction to higher math course now (mostly number theory) and our professor wants us to include two sentence proof synopses with our longer proofs. This got me thinking, What is a ...
5
votes
0answers
35 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
2
votes
0answers
38 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
17
votes
3answers
660 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
1
vote
3answers
245 views

Prove that no number in this list is prime - Formatting a proof advice

Question: Let $n \in \mathbb{Z}$ where $n \geq 2$, prove no number in the list: $$n! + 2, n! + 3,...,n! + n$$ is prime. I have written my proof exactly as follows: Proof: $P(n) = n! + n = ...
0
votes
1answer
45 views

How to show that if $ p \equiv 1,3 \pmod 8$ then there exists a $u,v \in \mathbb Z: u^2 + 2v^2 = p$

I'm trying to show this statement: $$p \equiv 1,3 \pmod 8, \; \; \exists \; u,v \in \mathbb Z : u^2 + 2 v^2 = p.$$ I believed I proved it the other direction using the ring $\mathbb Z{\sqrt{-2}}$. ...
0
votes
0answers
53 views

How can I prove that there are infinitely many primes of the form 4k-1? [duplicate]

I am trying to prove that there are infinitely many primes of the form $4k-1$. I am trying to make a contradiction by setting $N = 4p_1...p_k-1$ and supposing that there only finitely many primes of ...
3
votes
2answers
109 views

Proving an infinite number of primes of the form 6n+1

The proofs given on other sites weren't that clear and used different methods that I have yet to learn. Prove that there are an infinite number of primes of the form 6n+1. The hint that was given ...
3
votes
3answers
108 views

Proof that there are infinitely many primes congruent to 3 modulo 4

I'm having difficult proving this. As a hint the exercise to prove first, that if $a\lneqq \pm 1$ satisfies $a \equiv 3 (\textrm{mod}\ 4)$, then exist $p$ prime, $p \equiv 3 (\textrm{mod}\ 4)$ such ...
2
votes
1answer
42 views

Density of natural numbers

Let $A \subset \mathbb{N}$ and $D_A(n) = \dfrac{|A \cap [1,n]|}{n}$. One says $A$ has density if $\lim_n D_A(n)$ exists and is finite. I know there exist sets with and without density, and that ...
1
vote
6answers
225 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
1
vote
1answer
48 views

Prove or disprove: If $A$ and $B$ are denumerable, then $A - B$ is denumerable

Prove or disprove: If $A$ and $B$ are denumerable, then $A - B$ is denumerable Can someone give me a hint as to how to prove/disprove this? My instinct tells me that the claim is true. But I'm ...
1
vote
1answer
76 views

A polynomial is called a Fermat's polynomial…

A polynomial is called a Fermat polynomial if it can be written as the sum of the squares of two polynomials with integer coefficients. Suppose that $f(x)$ is a Fermat polynomial such that $f(0) = ...
1
vote
2answers
109 views

Primitive Roots Proofs

I am stuck on how to prove these two questions: (1) Let r be a primitive root of the prime $p$ with $p$ congruent to $1$ modulo $4$. Show that $-r$ is also a primitive root. (2) Let n be a positive ...
1
vote
0answers
72 views

How to say this proof correctly: if d|a and d|b then d|a-b.

I believe I have this proof solved, but not sure that I wrote it correctly. Given that $d|a$ then there exist a $n$ such that $n = dk$ for some $k$ Given that $d|b$ then there exist a $m$ such that ...
5
votes
5answers
245 views

Proving $n^3$ is even iff $n$ is even

I am trying to prove the following statement: Prove $n^3$ is even iff n is even. Translated into symbols we have: $n^3$ is even $\iff$ $n$ is even Since it's a double implication, I ...
2
votes
3answers
80 views

Prove that if $a|b$ and $a|c$, then $a\mid(c-b)$.

I'm having trouble proving this one. I know its true. Any ideas? Here is what I have so far: If $a\mid b$, then there exists an integer $q_1$ such that $b = aq_1$. If $a\mid c$, then there exists an ...
0
votes
3answers
161 views

If $n$ is an odd integer, then there exist integers $a$ and $b$ such that $n=a^2-b^2$. [duplicate]

If $n$ is an odd integer, then there exist integers $a$ and $b$ such that $n=a^2-b^2$. Am I supposed to use induction or a direct proof?
0
votes
0answers
41 views

Is this GCD proof valid?

I came across this theorem and wrote a proof, but I'm not sure if I made any incorrect assumptions. I also know that this isn't the easiest way to prove it - I just want to know if it works and ...
2
votes
3answers
112 views

Modular arithmetic

How do I prove the following inequality with modular arithmetic? (No use of Fermat's last theorem is allowed.) $$3987^{12} + 4365^{12} \neq 4472^{12}$$
2
votes
2answers
52 views

Proof of statement: If $a\mid b$ and $a\mid c$, then $a \mid b+c$

Statement: If $a$ divides both $b$ and $c$, then $a$ divides $b+c$ Proof: Assume that $a$ does not divide $b+c$. Then there is no integer $k$ such that $ak=b+c$. However, $a$ divides $b$, so $am=b$ ...
1
vote
1answer
85 views

How to write the proof for this?

Let $a,b,c \in \mathbb{Z}$, and $a \neq 0$. Use a proof by contradiction to show that if $(a \nmid (bc))$ then $(a \nmid b)$. The symbol $\nmid$ stands for "does not divide". I got the layout, but I ...
6
votes
5answers
278 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
0
votes
2answers
51 views

Is the proof of the claim correct? Is the claim true?

We say that an integer a is divisible by the nonzero integer b, if a = bc for some integer c: When a is divisible by b, we write b | a and say b divides a. Claim: Let a and b be nonzero integers. If ...
-2
votes
1answer
63 views

Contradiction Proof regarding Well-Ordering Principle

Let $r_0$ be the smallest element of a set $S$ such that $S\subseteq\mathbb {N} \cup \{ 0 \}$. According to the Well-Ordering Principle, this implies that $r_0$ $\ge 0$ and $r_0 = a - q_0 b$ for some ...
4
votes
2answers
741 views

Prove that there exist no positive integers $m$ and $n$ for which $m^2+m+1=n^2$

The problem: Prove that there exist no positive integers $m$ and $n$ for which $m^2+m+1=n^2$. This is part of an introductory course to proofs, so at this point, the mathematical machinery should not ...
0
votes
4answers
125 views

Why is $n^2 - 2$ never a multiple of $3$?

I know that for any $n$, $n^2 - 2$ is never a multiple of $3$. I feel like this is a rather simple proof, but I cannot figure out how to manipulate the definition of a multiple of $3$: $n$ is a ...
1
vote
2answers
330 views

Prove, for any positive integer $n$, that $n -3$ must be a multiple of $5$ if $n^3 -n -4$ is a multiple of $5$.

I had previously solved the problem of proving that $n^3-n-4$ must be a multiple of $5$, given that $n-3$ is a multiple of $5$. I did so by algebraically manipulating $n^3-n-4$ into: $$ ...
5
votes
5answers
219 views

Show that $\gcd(a,b)=\operatorname{lcm}(a,b)$ if and only if $a=b$.

I know how to prove $a=b$ only if $\gcd(a,b)=\operatorname{lcm}(a,b)$, but I don't know how to prove the "if part". Can anyone help me?
1
vote
1answer
76 views

Proof Checking and input: Generators of $\mathbb{Z}_{pq}$

I'm self-studying abstract algebra (slowly but surely), and I have a question about my answer to the following prompt: Problem statement: Show that there are $(q-1)(p-1)$ generators of the group ...
5
votes
1answer
196 views

Dividing Squares Fails to Invoke Contradiction: Two Elementary Divisibility Proofs

$x^2 \text{ is even } \iff x \text{ is even } \tag{Thm 3.12, P76}$ $\text{ Let } x, y \in \mathbb{Z}. \text{ Then } x \;\& \; y \text{ are of the same parity } \iff x + y \text{ is even.} \tag{Thm ...
13
votes
2answers
197 views

Question from Putnam '89: Primes of the form $101\ldots01$

I'm not a math major, but would like to compete in the Putnam. As suggested in other questions here, I'm working some old contest problems. I'd like some input on this attempted proof--general input ...
1
vote
1answer
52 views

If $p$ is irreducible and $p \not \mid a$, then $\text{gcd}(p,a)=\pm 1$.

I will be taking a Rings and Fields course in the Fall, so I figured I would read ahead in the textbook (A First Course in Abstract Algebra, by Anderson and Feil) to prepare. Recall the following ...
2
votes
0answers
56 views

Is my proof correct? (Also formally)

Hello dear community! I just worked on a problem in my discrete mathematics text book and wondered if my approach to a specific exercise is correct. There are no solutions to it, that's the reason I ...
2
votes
1answer
441 views

Help understanding the proof of Lame's Theorem.

I think Lamé's Theorem is beautiful and really want to understand the proof. I am new to proofs, but after reading over the proof of Lamé's Theorem (and failing to understand it), I feel that I am ...
1
vote
0answers
56 views

Translation/proof of elementary argument of Chebyshev

My question is whether the following proof is correct and how it might be better presented. This was an exercise to translate/shorten Chebyshev's argument that $\hspace{80mm} (1)$ $\hspace{55mm}\log ...
0
votes
4answers
83 views

Show that $5^n + 6^n = 0 \pmod{11}$ for all odd $n$

show that $5^n + 6^n = 0 \pmod{11}$ for all odd number $n$, but not for any even number $n$. I was not sure about this question. Do I have to pick numbers for $n$? Until I get odd number?
14
votes
3answers
240 views

Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$

For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$. I used induction principle for the solution but cannot prove it. I took $P(k) = ...
29
votes
5answers
5k views

Are all prime numbers finite?

If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid ...
2
votes
1answer
85 views

how to show associativity of multiplication for not just 3 operands but for n operands

ie Id like to show a(bc)=(ab)c but for any n operands eg abcdefg=gfdcabe etc I can see this is very intuitive that this should be true for all n operands, but as a logical exercise I would like to ...
1
vote
1answer
62 views

Proof Technique and Factorials

I need to prove that $\;n!+m$ is divisible by $m$ for all integers $n \ge 2$ and $1 \le m \le n$.
3
votes
4answers
636 views

Proof by induction; $a^n$ divides $b^n$ implies $a$ divides $b$

I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$. clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$. Suppose this is true ...
5
votes
5answers
127 views

Proving $n+3 \mid 3n^3-11n+48$

I'm really stuck while I'm trying to prove this statement: $\forall n \in \mathbb{N},\quad (n+3) \mid (3n^3-11n+48)$. I couldn't even how to start.
1
vote
3answers
1k views

Proving That The Product Of Two Different Odd Integers Is Odd

Okay, here is how I begin my proof: Let $q$ and $r$ be odd integers, then $q = 2k+1$ and $r = 2m+1$, where $k,m \in Z$. $q \times r = (2k+1)(2m+1) \implies q \times r = 4mk + 2k + 2m + 1 \implies q ...
1
vote
1answer
152 views

Are there any errors in my proof that only perfect squares have rational square roots?

This is a very simple proof, but I know that proofs which are this simple can often have some erroneous assumptions. Is mine okay? Argument: With the exception of perfect squares, there are no ...
3
votes
1answer
57 views

How might one go about proving this poorly worded theorem about divisibility with the number 3?

I was messing around and found something interesting, at least to me. Although I may not know how to delicately word this, so I hope it is clear. Claim: Each natural number $n$, whose sequence of ...
8
votes
3answers
288 views

Proof of Wolstenholme's theorem.?

According to the theorem : $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$ And we have to prove that $r= 0 \pmod{p^2}$. (Given $ p>3$, ...
1
vote
2answers
98 views

Prove by contradiction

Let $$ A = \cfrac {r_1 + r_2 + r_3 + \ldots + r_n}{n} $$ be the average of the real numbers $r_1, \ldots , r_n$. Prove there exists $i$ such that $r_i \ge A$. So this is obviously true because the ...