# Tagged Questions

59 views

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 ...
58 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 ...
67 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 ...
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 ...
31 views

53 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}}$. ...
59 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 ...
235 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 ...
265 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 ...
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 ...
260 views

141 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 ...
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 ...
249 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 ...
86 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 ...
172 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?
45 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 ...
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}$$
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$ ...
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 ...
301 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 ...
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 ...
71 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 ...
833 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 ...
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 ...
351 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:  ...
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?
### 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 ...