2
votes
1answer
60 views

Prove $ x^n-1=(x-1)(x^{n-1}+x^{n-2}+…+x+1)$

So what I am trying to prove is for any real number x and natural number n, prove $$x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1)$$ I think that to prove this I should use induction, however I am a bit stuck ...
1
vote
1answer
60 views

Proof by contradiction: logarithm

I need to prove by contradiction that $\log_2(3)$ is irrational. I'm really unfamiliar with logs to be honest, it's been awhile since I've done them and I'm unsure of how to approach this. Any help ...
0
votes
2answers
63 views

Proof that doesn't exists a rational $s$ such that $s^2 = 6$

Well, I solved it, and I would like to know if there is anything that can be corrected or improved here. I think that the proof ended up too long, and with too many letters. Surely there is a better ...
2
votes
5answers
69 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
0
votes
2answers
35 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
1
vote
1answer
32 views

Prove that $\dfrac{\sigma_1(n)}{n} = \sigma_{-1}(n)$ where $\sigma_x(n)$ is the sum of the $x$th powers of the positive divisors of $n$.

I computed $\dfrac{\sigma_1(n)}{n}$ and $\sigma_{-1}(n)$ on a good hundred values of $n$, and they seem to always match. For example: $\dfrac{\sigma_1(6)}{6} = \dfrac{1 + 2 + 3 + 6}{6} = ...
1
vote
0answers
40 views

What is the relationship between division and proving an integer is odd?

I am trying to use proof by contradiction to prove: $101$ is an odd integer. I know that the first step is to assume that $101$ is even, so: $101 = 2q, q \in \mathbb{Z}$ Then I am stuck. I don't ...
1
vote
3answers
62 views

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ [duplicate]

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ How would you do the inductive step for this proof? I have the base case done.
0
votes
2answers
86 views

Prove that if $n^2 - 1$ is divisible by a prime number $p$ such that $n - 1$ is not divisible by $p$, then $n + 1$ is also divisible by $p$.

If this proposition is false, please give at least $3$ counter-examples, and try to modify the proposition so that it becomes true. If the proposition is true, please try to prove this even more ...
1
vote
5answers
98 views

If $a, b$ are relatively prime proof.

Prove that if $a$ and $b$ are relatively prime integers and $ab$ is a perfect square so are $a$ and $b$. Show by counterexample that the relatively prime condition is necessary. I dont know how ...
-3
votes
2answers
36 views

Proofs for modular arithmetic

$\rm(a)$ Prove that for any pair $a,b$ of positive integers there are integers $x,y\in\Bbb Z$ such that $ax+by=\gcd(a,b).\ $ (Hint: Use the well-ordering principle on the set of integer linear ...
-1
votes
3answers
112 views

Prove that if $n+1$ is divisible by $m$ then $n^2-1$ is also divisible by $m$. [closed]

Prove that if $n+1$ is divisible by $m$ then $n^2-1$ is also divisible by $m$. And prove that if $n^2-1$ is divisible by $m$ then $n+1$ is also divisible by $m$.
2
votes
1answer
93 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
5
votes
1answer
95 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
104 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
92 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 ...
6
votes
0answers
76 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
49 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, ...
18
votes
3answers
726 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
254 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
55 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}}$. ...
3
votes
2answers
293 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 ...
4
votes
3answers
277 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
45 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
271 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
100 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
95 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
144 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
252 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
87 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
173 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
47 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
114 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}$$
3
votes
2answers
56 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
86 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
304 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
53 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
72 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
853 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
130 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
354 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: $$ ...
6
votes
5answers
228 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
83 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
207 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
224 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
53 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
58 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 ...
4
votes
1answer
611 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
58 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 ...