Articles of elementary number theory

On modular roots of $-1$?

Given $n\in\Bbb N$ what is the best method to find if there is an $x\in\Bbb Z_n$ such that $x^2\equiv-1\bmod n$? I mean supposing we have $x^2\equiv-1\mod p$ how to find that $x$ when $p$ is a prime?

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I’m not sure how to use that information if I even can to show that $p^n \mid a^n$.

For any prime number $p$ and natural number $i < p$, prove that $p$ divides ${p \choose i}$.

This question already has an answer here: Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$ 5 answers

Conjecture about linear diophantine equations

I’ve been dabbling with linear Diophantine equations and came across a rather interesting pattern that I would like to conjecture as true but I have no idea how about to come up with a proof. Let $ax+by=c$ be the linear Diophantine equation such that $gcd(a,b)=1$. Obviously $1|c$ so there are solutions to the equation. If […]

Show that ${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$

This question already has an answer here: Evaluating even binomial coefficients 5 answers Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$ 7 answers

“Descent” on binary quadratic forms?

Let’s say I have the Diophantine equation $$ x^2+3n^2 = y^2+3z^2. \tag{$\star$} $$ where $n$ is a known integer, and we’re trying to determine solutions in integers $x,y,z \ge 1$. Rewrite ($\star$) as $$ x^2 – 3z^2 = y^2 – 3n^2 = k, \tag{$\dagger$} $$ where $k$ is some unknown integer. For simplicity’s sake, let’s […]

Solving the Diophantine equation $x^n-y^n=1001$

For all $n \in \mathbb{N}$, solve the Diophantine equation $x^n-y^n=1001$, where $x,y \in \mathbb{N}$. The cases $n=1,2$ are trivial ones. But for $n>2$ I can’t find any solutions. How could I prove that there are no integer solutions for $n>2$?

How to use well-ordering to form a “least counterexample derived contradiction” to prove rule for obtaining the remainder when dividing $3^n$ by 13?

By the division with remainder theorem, we know that there exists $q \in \mathbb{Z}$ and $r \in \mathbb{Z}$, where $0 \leq r < 13$, such that: \begin{equation*} 3^n = 13q + r \end{equation*} Simple rule for obtaining remainder when dividing $3^n$ by $13$: it can be shown then, that $r = 3^p$, where $p = […]

Proving that $a,n$ and $b, n$ relatively prime implies $ab,n$ relatively prime

Question: Suppose $a,b \in \Bbb N$, $\gcd (a,n) = \gcd(b,n) = 1$. The question is to prove or give a counterexample: $\gcd(ab,n) = 1$. My Work: This is what I have so far (for $\alpha, \beta, \gamma, \delta \in \Bbb Z$): \begin{align*} \gcd(a,n) = 1 \ &\Rightarrow 1 = \alpha a + \beta n\\ \gcd(b,n) […]

If $d=\gcd\,(f(0),f(1),f(2),\cdots,f(n))$ then $d|f(x)$ for all $x \in \mathbb{Z}$

$\textbf{Question.}$ Let $f$ be a polynomial of degree $n$ which takes only integral values. If $d=\gcd\,\{f(0),f(1),f(2),\cdots,f(n)\}$ then show that $d|f(x)$ for all $x \in \mathbb{Z}$. How can one show this. It’s clear that if $f$ has degree $1$, then $f(x)=a_{0}+a_{1}x$. Clearly we have $d|a_{0}$ and $d|a_{0}+a_{1}$ so we have $d\mid a_{1}$, this says $d\mid f(x)$ […]