Intereting Posts

Can someone explain the Yoneda Lemma to an applied mathematician?
Calculating the group co-homology of the symmetric group $S_3$ with integer coefficients.
Why is the Relation R4 Reflexive?
For $F$ closed in a metric space $(X,d)$, is the map $d(x,F) = \inf\limits_{y \in F} d(x,y)$ continuous?
Complex Analysis: Liouville's theorem Proof
What is the fastest way to multiply two digit numbers?
How to prove that the rank of a matrix is a lower semi-continuous function?
Does a closed form for this specific integer sequence exist?
Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
Find a continuous function $f:[1,\infty)\to\Bbb R $ such that $f(x) >0 $, $\int_1^\infty f(x)\,dx $ converges and $\int_1^\infty f(x)^2\,dx$ diverges
Bound for the degree
An $r\times r$ submatrix of independent rows and independent columns is invertible (Michael Artin's book).
Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?
Non-standard models for Peano Axioms
Affine plane of order 4?

I want to prove that if $n^2$ is even then $n$ is even directly without using the contrapositive or the contradiction methods.

- A doubt with a part of a certain proof.
- Permutation Partition Counting
- $\lfloor a n\rfloor \lfloor b n\rfloor \lfloor c n\rfloor = \lfloor d n\rfloor \lfloor e n\rfloor \lfloor f n\rfloor$ for all $n$
- Prove that 10101…10101 is NOT a prime.
- What is a good book to learn number theory?
- Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?
- Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.
- Some trigo identities
- Why does $(\frac{p-1}{2}!)^2 = (-1)^{\frac{p+1}{2}}$ mod $p$?
- Finding integers of the form $3x^2 + xy - 5y^2$ where $x$ and $y$ are integers, using diagram via arithmetic progression

**Hint** $\ $ Induction yields a direct proof: $\rm\ 2\ |\ n^2\:\Rightarrow\:2\ |\ n\:$ is true for $\rm\:n = 0,1\:$ so $\rm\color{red}{induction}$ yields

$$\rm 2\ |\ (n+1)^2 = (n-1)^2 + 4n\ \Rightarrow\ 2\ |\ (n-1)^2\ \color{red}{\Rightarrow}\ 2\ |\ n-1\ \Rightarrow\ 2\ |\ n+1$$

Similarly one may prove $\rm\: 2\ |\ nk\:\Rightarrow\: 2\ |\ n\ \ or\ \ 2\ |\ k\ $ (Prime Divisor Property for $\rm\:p = 2$) via

$$\rm\ 2\ |\ (n+1)k = (n-1)k + 2k\ \Rightarrow\ 2\ |\ (n-1)k\ \color{red}{\Rightarrow}\ 2\ |\ n-1\ \ or\ \ 2\ |\ k\ \Rightarrow\ 2\ |\ n+1\ \ or\ \ 2\ |\ k$$

Note that your problem is the special case $\rm\ k = n\ $ of the Prime Divisor Property for $\:2$.

Note that the proof is essentially a brute-force case-analysis. It verifies the result for a complete system of least residues modulo $2,\:$ viz. $\rm\:0,1,\:$ and then, by induction, lifts this proof to all naturals, using the fact that the property $\rm\:P\:$ is true for $\rm\:n\:$ implies that it is true for $\rm\:n+2,\:$ i.e.

$$\rm P(0),\ P(1),\ [P(n)\Rightarrow P(n+2)]\ \Rightarrow\ \ \forall n\: P(n)$$

Similarly there are brute-force residue case-analyis proofs of the prime divisor property for any fixed prime (as known to the ancient Greeks). Such proofs amount to brute-force checking all entries of the multiplication table for integers modulo p, to verify that a product is zero implies that some factor is zero. But proving this true for *all* primes requires a new idea. For the integers this idea is that gcds exist for all naturals (by the Euclidean algorithm), hence

$$\rm\:p\ |\ ab\ \Rightarrow\ p\ |\ pb,ab\ \Rightarrow\ p\ |\ gcd(pb,ab) = \gcd(p,a)b\:$$

$\rm p\:$ prime $\Rightarrow$ $\rm gcd(p,a) = p\ or\ 1$. $\rm\:gcd(p,a)=p\:$ $\Rightarrow$ $\rm\:p\:|\:a.\:$ $\rm\:gcd(p,a)=1\:$ $\Rightarrow$ $\rm\:p\:|\:gcd(p,a)b = b.$

Hence we’ve proved: $\:$ prime $\rm p\ |\ ab\ \Rightarrow\ p\ |\ a\ \ or\ \ p\ |\ b\quad\ \ $ **[Prime Divisor Property for $\mathbb Z\:$]**

This prime divisor property is easily shown to be equivalent to the *uniqueness* of factorizations into irreducibles. In domains that don’t have unique factorization, irreducibles need not satisfy the prime divisor property. In such general domains, the term “prime” is used to denote those irreducibles that do satisfy the prime divisor property

The same proof as above shows that irreducibles satisfy the prime divisor property in any integral domain where gcds exist, e.g. *Euclidean* domains which, like $\mathbb Z$, enjoy a Division Algorithm. One well-known example is the ring $\rm F[x]$ of polynomials over a field $\rm F,\:$ which enjoy the high-school polynomial long division algorithm.

$n^2+n=n(n+1)$ is even; therefore, $n^2$ and $n$ have the same parity.

This is easily possible using prime factor decomposition. Just consider how often the prime factor “2” occurs in $n^2$ and deduce that 2 divides $n$.

**Hint:** Let $n^2$ be even. Then $n^2=2k$, for some integer $k$. Moreover, by the *Fundamental Theorem of Arithmetic*, $n^2$ has prime-power decomposition $n^2=\left(p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}\right)^2=p_1^{2a_1}p_2^{2a_2}\cdots p_s^{2a_s}$, for some positive integers $s$ and $a$.

One can show that if $(a,b)=1$ and $a|bc$ then $a|c$.

Proof: If (a,b)=1 then $ax+by=1$ for integers $x,y$. We also have $bc=ka$ for some integer $k$, but then $c=1a=acx+bcy=a(cx+ky)$. Hence $a|c$.

Now for any prime $p$ and integer $n$ we have $(p,n)=1$ or $(p,n)=p$. In either case $p|n$. Putting in your particular example of $p=2$ yields want you want.

Here’s a proof by induction. It’s similar to Bill’s proof but doesn’t use the Prime Divisor Property.

$P(n)$: $n^2$ is even iff $n$ is even.

Proof:

$(n=1)$: ”$1^2$ is even” and ”$1$ is even” are both false so $P(1)$ is true.

(Inductive step): Assume $P(n)$: $n^2$ is even iff $n$ is even.

Now assume $(n+1)^2$ is even. Then $n^2 + 2n + 1$ is even which means that $n^2$ is odd. By the induction hypothesis $n$ is odd, in which case $n+1$ is even. On the other hand, if $n+1$ is even, then clearly $(n+1)^2$ is even.

This completes the proof.

- My incorrect approach solving this limit. What am I missing?
- Show that a sequence of functions convergent pointwise to $\chi_{\mathbb Q}$ does not exist
- The Chinese remainder theorem and distributive lattices
- Can any infinite ordinal be expressed as the sum of a limit ordinal and a finite ordinal?
- Showing the exponential and logarithmic functions are unique in satisfying their properties
- Closed form of the sequence $a_{n+1}=a_n^2+1$
- Analytic $F(z)$ has $f(z)$ as derivative $\implies$ $\int_\gamma f(z)\ dz = 0$ for $\gamma$ a closed curve
- What is the smallest value of $n$ for which $\phi(n) \ne \phi(k)$ for any $k<n,$ where $n=4m$?
- Can Markov Chain state space be continuous?
- Non-associative version of a group satisfying these identities: $(xy)y^{-1}=y^{-1}(yx)=x$
- Finding divisibility of a
- (non?)-surjectivity of the exponential map to $SL(2,\mathbb{C})$
- Does zero distributional derivative imply constant function?
- Find all the solutions of $6a+9b+20c=-2$
- Find the probability mass function of the (discrete) random variable $X = Int(nU) + 1$.