Tag Info

Hot answers tagged

17

Write $n=3r+q$ with $q\in\{0,1,2\}$. Then $$ n^2+4=9r^2+6rq+q^2+4=(9r^2+6rq+3)+q^2+1. $$ The expression in the parentheses is divisible by $3$ whereas inspecting the three possibilities for $q$ reveals that $q^2+1$ is never divisible by $3$.


8

For any integer $n$ we have, $$n\equiv\{0,1,2\}\pmod3\implies n^2\equiv \{0,1,4\}\equiv \{0,1,1\}\equiv\{0,1\}\pmod3\\ \implies n^2+4\equiv\{4,5\}\equiv\{1,2\}\pmod3\implies n^2+4\not\equiv0\pmod3$$ $$\therefore\quad 3\not\mid n^2+4~\forall~n\in\Bbb{Z}$$


7

Definitions are just shorthand. For example "$f$ is a function from $A$ to $B$" is shorthand, in set theory, for $$f\subseteq A\times B \land \left(\forall x(x\in A\implies\exists_1 y((x,y)\in f))\right)$$ And here, even $\exists_1$ is a shorthand. Definitions are a way to avoid writing the same thing over and over again. Another example: Saying "$p,q$ ...


5

Look at the expression mod $3$, $$n^2 + 4 \equiv n^2 + 1.$$ Could $n^2\equiv 2$? What are the squares mod $3$? $0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4 \equiv 1$. Thus $2$ isn't a square mod $3$!


4

The question of proof equivalence is quite an old one! In fact, David Hilbert considered adding it (or a similar one) to his celebrated list of open problems, but finally decided to leave it out, so it is sometimes referred to as Hilbert's 24th problem. There is a rather well-established field investigating proof equivalence, though definitely no clear ...


3

What definitions are in the most primitive sense (mathematical and linguistic): Definition, n. $\qquad$ The settings of bounds or limits; limitation, restriction. The above is the primary meaning of definition from the authoritative Oxford English Dictionary. Of course, you are more interested in the role(s) of definitions in mathematics. The following ...


3

Consider cases. For example, what happens if $n=3k$, $n=3k+1$, and $n=3k+2$?


1

General question: For which odd primes $p$ does $n^2+m^2 \equiv 0 \bmod p$ have solutions, where $m$ is coprime to $p$? $n^2+m^2 \equiv 0 \implies n^2 \equiv -m^2$ In order for $-m^2$ to be a quadratic residue $\bmod p$, Euler's criterion requires that $(-m^2)^{\frac{p-1}{2}} \equiv 1$. However we already know that Euler's criterion holds for $m^2$, so ...


1

Answer using Quadratic Reciprocity. We use Euler's criterion, which states that $n \in \mathcal QR(p)$ iff $n^{\frac {p-1}{2}} \equiv 1 \bmod p$. We use the Legendre symbol $(\frac np) = \begin{cases} 1 \text{, n} \in \mathcal QR(p)\\ -1 \text{, n} \in \mathcal NR(p)\end{cases}$ for the sake of contradiction, assume $3 \mid n^2+4$ $3 \mid n^2+4 ...


1

Your proof is correct, but there is no reason to use contradiction here: it just makes the argument unnecessarily complicated. You’ve basically taken the natural direct proof and turned it into a proof by contradiction. We know that $g\mid x$, so there is an integer $m$ such that $x=mg$. Similarly, there is an integer $n$ such that $y=ng$. But then ...


1

Base Step: $2 \cdot 3^{1-1} = 2 = 3^1 - 1$ The inductive hypothesis is: $\sum_{n=1}^{k} 2 \cdot 3^{n-1} = 3^k - 1$ We must show that under the assumption of the inductive hypothesis that $$3^k - 1 + 2 \cdot 3^k = 3^{k + 1} - 1$$ We verify this as $$3^k - 1 + 2 \cdot 3^k = 3^k(1 + 2) - 1$$ $$= 3^{k+1} - 1$$


1

For any $n \in \mathbb{N}$, we have $ n \equiv 0,1,2 \text{ mod } 3 $. Hence $ n^2 \equiv 0,1 \text{ mod } 3 $. Thus $ n^2+4 \equiv 1,2 \neq 0 \text{ mod } 3 $. So for any integer $n \in \mathbb{N}$ , $ n^2+4$ is not divisible by $3 $.


1

Maybe there is a confusion here between definitions and axioms. In the former, we do not assume somethings exists when defining it, we just ascribe it a name. In the latter, we postulate that some sentence holds. Take the following example in ZFC: $\text{Axiom of Existence}: \text{there exists a set with no elements}$ Here we postulate existence of a ...


1

This proof irrelevance is one of the problems of classic foundations. In Type Theory, however, we represent mathematical statements as types, which enables us to treat proofs as mathematical objects. This is because of a well-known isomorphism between types and propositions a.k.a. Curry-Howard Correspondence, which roughly says that to find a proof of a ...


1

See : Joseph Shoenfield, Mathematical logic (1967), page 27, for the : Tautology Theorem : If $B$ is a tautological consequence of $A_1,\ldots,A_n$, and $\vdash A_1, \ldots, \vdash A_n$, then $\vdash B$. Thus, due to the fact that $A∨(B∨C)$ is a tautological consequence of $(A∨B)∨C$, by the above theorem we conclude with the "derived rule" : if ...


1

The infinite monkey theorem states that if you have an infinite number of monkeys each hitting keys at random on typewriter keyboards then, with probability 1, one of them will type the complete works of William Shakespeare. Let $A_n$ be the event that the $n^{th}$ monkey types the complete works of Shakespeare. Then if there are $m$ characters on the ...


1

The short intuitive answer is that if $A=B$ then $cA=cB$ for any $c$. This must be the case for multiplication to be well-defined. Though $A$ and $B$ may be written differently, they are in fact the same number. If multiplication is well defined then when I multiply $c$ by something, say $A$, it shouldn't matter how I've written $A$, or what day of the ...



Only top voted, non community-wiki answers of a minimum length are eligible