# Tagged Questions

44 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}}$. ...
50 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 ...
81 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 ...
49 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 ...
41 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 ...
181 views

93 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 ...
243 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 ...
71 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 ...
156 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?
40 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 ...
111 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}$$
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$ ...
81 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 ...
261 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 ...
49 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 ...
61 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 ...
654 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 ...
122 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 ...
316 views

51 views

### Congruence relationships.

I need to prove (or disprove but I don't think that's the case) that: if $ab \equiv 0$ (mod $n$), then $a\equiv 0$ (mod $n$) or $b\equiv0$ (mod $n$) I know that $ab\equiv 0$ (mod $n$) ...