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?

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$.

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

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 […]

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

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 […]

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$?

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 = […]

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) […]

$\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)$ […]

Intereting Posts

Number of elements in the quotient ring $\mathbb{Z}_6 /\langle 2x +4\rangle$
Every power series is the Taylor series of some $C^{\infty}$ function
Where can I find SOLUTIONS to real analysis problems?
common knowledge and concept of coarsening partition
Bijection from finite (closed) segment of real line to whole real line
Distance minimizers in $L^1$ and $L^{\infty}$
Is it always true that if $\gcd(a,b)=1$ then $\gcd(ab, c) = \gcd(a, c)\gcd(b, c)$?
A minimization problem in function fitting setup
Bayesian Parameter Estimation – Parameters and Data Jointly Continuous?
A set is infinite iff it is equivalent to a proper subset of itself
martingale and filtration
Construct a metric for the topology of compact convergence on $Y^{X}$ so that $Y^{X}$ is complete when $(Y,d)$ is complete and $X$ is $\sigma$-compact
Rationalizing expressions
Why are mathematical proofs that rely on computers controversial?
Why can 2 uncorrelated random variables be dependent?