Articles of elementary number theory

Fermat: Prove $a^4-b^4=c^2$ impossible

Prove by infinite descent that there do not exist integers $a,b,c$ pairwise coprime such that $a^4-b^4=c^2$.

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it’s fairly simple to see why they work, but the hard part is proving all non-powers of 2 don’t work. In the solution, it says “If $n$ is not a […]

Problem from Olympiad from book Arthur Engel

Each of the numbers $a_1 ,a_2,\dots,a_n$ is $1$ or $−1$, and we have $$S=a_1a_2a_3a_4+a_2a_3a_4a_5 +\dots+ a_na_1a_2a_3=0$$ Prove that $4 \mid n$. If we replace any $a_i$ by $−a_i$ , then $S$ does not change $\mod\, 4$ since four cyclically adjacent terms change their sign. Indeed, if two of these terms are positive and two negative, […]

Necessary and sufficient conditions for the sum of two numbers to divide their product

How to find necessary and sufficient conditions for the sum of two numbers to divide their product. Thanks in advance.

Counting the number of integers $i$ such that $\sigma(i)$ is even.

Define $\sigma(i)$ to be the sum of all the divisors of $i$. For example, $σ(24) = 1+2+3+4+6+8+12+24 = 60$. Given an integer $n$, how can we count the number of integers $i$, less than or equal to $n$, such that $\sigma(i)$ is even?

Prove that the congruence $x^2 \equiv a \mod m$ has a solution if and only if for each prime $p$ dividing $m,$ one of the following conditions holds

Let $m$ be odd and let $a \in \mathbb{Z}.$ The congruence $x^2 \equiv a \mod m$ has a solution if and only if for each prime $p$ dividing $m,$ one of the following conditions holds, where $p^{\alpha} \mid \mid m$ and $p^{\beta}\mid \mid a$: $\beta \geqslant \alpha$; $\beta < \alpha$, $\beta$ is even, and $a/p^{\beta}$ […]

If $a^m-1 \mid a^n -1$ then $m \mid n$

This question already has an answer here: Showing that $a^n – 1 \mid a^m – 1 \iff n \mid m$ 3 answers

Find all primes $p$ such that $14$ is a quadratic residue modulo $p$.

I want to find all primes $p$ for which $14$ is a quadratic residue modulo $p$. I referred to an example that was already posted for finding all odd primes $p$ for which $15$ is a quadratic residue modulo $p$, but I am getting stuck. This is what I have done: $$\left(\frac{14}{p}\right)=\left(\frac{7}{p}\right)\left(\frac{2}{p}\right)=(-1)^{(p-1)/2}\left(\frac{p}{7}\right)\left(\frac{p}{2}\right). $$ There are […]

Easiest proof for $\sum_{d|n}\phi(d)=n$

This question already has an answer here: Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$? 6 answers

Solving a Diophantine Equation

Let $p \equiv q \equiv 3 \pmod 4$ for distinct odd primes $p$ and $q$. Show that $x^2 – qy^2 = p$ has no integer solutions $x,y$. My solution is as follows. Firstly we know that as $p \equiv q \pmod 4$ then $\big(\frac{p}{q}\big) = -\big(\frac{q}{p}\big)$ Assume that a solution $(x,y)$ does exist and reduce […]