# Questions tagged [elementary-number-theory]

Questions on congruences, linear Diophantine equations, greatest common divisor, divisibility, etc.

26,633 questions
Filter by
Sorted by
Tagged with
48 views

### How do I prove the following properties about prime numbers?

Let $p$ be a prime number not equal to 2 or 3 Prove that $p\equiv 1\pmod{6}$ or $p\equiv -1\pmod{6}$ Prove that if $p+2$ is also a prime,then $p+1$ is divisible by 6
38 views

### How to check if N is prime or not، when you have the factors of (N-1) [on hold]

How to check if (N) prime or not, using $N-1$ factors, pocklington primality test for example can be used to check these numbers, is there any other methods ?
81 views

### Diophantine equation: $n^2=c(4ab-a-b)-b$?

Let $n$ be a positive integer. The Diophantine equation $$n^2=c(4ab-a-b)-b,\qquad (a,b,c\in\mathbb{Z}^+)$$ is solvable for $n\equiv\pm1\pmod3$, but I stuck for $n\equiv0\pmod3$. Is there any ...
84 views

### Compute $\gcd(a+b, 2a+3b)$ if $\gcd(a,b) = 1$

A question from a problem set is asking to compute the value of $\gcd(a+b, 2a+3b)$ if $\gcd(a+b) = 1$, or if it isn't possible, prove why. Here's how I ended up doing it: $\gcd(a,b) = 1$ implies ...
219 views

### How to find the consecutive odd numbers that sum to a given odd number

Given an non perfect square odd number, say $1649$ What is the most efficient way to find the consecutive odd positive integers that sum to that number. No other information is provided, just the odd ...
86 views

### Proof explanation: suppose $a\mid bc$ and $\gcd(a, b) = 1$. Then $a\mid c$.

I have been given a proof, but I do not understand the "why" behind it. If someone could explain me each of its steps with great detail that would be amazing! The proof I was given is the following ...
89 views

### Is every prime contained in the set $\,\{n\in\mathbb{N}:n|10^k-1\}\cup\{2,5\}\,$ for $k=1,2,3,…$?

Is every prime contained in the set $\,\{n\in\mathbb{N}:n|10^k-1\}\cup\{2,5\}\,$ for $k=1,2,3,...$? Let $p\notin\{2,5\}$ be a prime number. Then $\frac{1}{p}$ has a decimal period of length at most ...
62 views

134 views

### If $a \equiv b \pmod n$ and $c+d = n$, does $ca+bd \equiv 0 \pmod n$?

I am trying to prove a different equation and am able to if the following is true, but I am not exactly sure if it is true. If $a\equiv b \pmod{9}$ and $c+d = 9$, is $ca+bd \equiv 0 \pmod{9}$ a true ...
224 views

64 views

### How many odd twin composite pairs are there?

I was wondering, if there is a formula to determine how many odd composite pairs there are until a given $n\in\mathbb{Z}^+$ like $(25,27), (33,35), etc.$ Theoretically it can be calculated, because ...
72 views

### Solving $84m+165n=117$ over $\mathbb{Z}$

I have two integers $m,n\in \mathbb{Z}$ and I would like to find in order to solve the following equation over $\mathbb{Z}$: $$84m+165n=117$$ I guess we need to use the Euler algorithm but I'm not ...
57 views

### Factors of binomial coefficients [on hold]

I am looking for some ideas to prove or disprove the following conjecture: Let $p$ be a an odd positive integer. Then $2^n$ divides $\binom{2^np}{k}$ for any integer $0<k<2^np$. Thanks for ...
### Can at least one primitive root $w$ of $N$ be expressed as $a^2-b$, where $(b|N)=-1$
I am stuck on a thought experiment: can any (or for that matter, at least one) primitive root $w$ of $N$, $N$ prime, be expressed as $w=a^2-b$, where $(b|N)=-1$, and $a,b\in\mathbb{N}$. We know that ...