# Questions tagged [elementary-number-theory]

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

26,620 questions
Filter by
Sorted by
Tagged with
28 views

### Prove that $(a+b)/(c+d)$ is a fraction in lowest terms if $ad − bc = 1$. [duplicate]

I have deduced that the $gcd(a,b)=1$ and the $gcd(c,d)=1$. I also figure since $(a+b)/(c+d)$ is a fraction in lowest terms $gcd(a+b,c+d)=1$ but from there I really have no idea what to do.
866 views

### Number Theory Homework: Find 3 consecutive integers…

I have this problem assigned for homework, and I'm a bit confused as to how to solve it: Obtain three consecutive integers, the first of which is divisible by a square, the second by a cube, and the ...
84 views

### Has $n^{n+1}+(n+1)^{n+2}$ other obvious factors than that I found?

Has the number $$f(n):=n^{n+1}+(n+1)^{n+2}$$ "obvious" factors (algebraic, aurifeuillan or similar kinds) apart from those , I mention below ? I only managed to find out forced factors for odd ...
43 views

### Does there exist some prime $k$ for which there will be exactly two primes of the form $n!+k$?

This is a question related to my recent question Conjecture: “For every prime $k$ there will be at least one prime of the form $n!\pm k$” true? Using PARI/GP I searched for the number of primes of ...
167 views

128 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 ...
211 views

55 views

54 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 ...
270 views

### Quadratic field, $O_K/\mathfrak{p} = \mathbb{F}_p$, $O_K/pO_K$ is a finite field of order $p^2$.

Let $K$ be a quadratic field $\mathbb{Q}(\sqrt{m})$ where $m$ is a square free integer, and let $p$ be a prime number which does not divide $2m$. Where can I find a reference to a proof of the ...
138 views

### What is known about the minimal number $f(n)$ of geometric progressions needed to cover $\{1,2,\ldots,n\}$, as a function of $n$?

So a geometric progression can contain at most two primes. This automatically gives a lower bound on the minimal number $f(n)$ of geometric progressions needed to cover the integers $\{1,2,\ldots,n\}$,...
22 views

### 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 ...
54 views

### Are there nontrivial perfect powers of integers that are nontrivial repdigits?

For example, $6^5=7776$ is close, but not quite a repdigit. Heuristically, it seems to me that there should not be any, because the longer a number with (effectively) random digits is, the less the ...
51k views

### What is meant by “evenly divisible”?

"What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?" Is it different from divisible?
46 views

### Structure of integer pairs which commute under exponentiation

In the natural numbers, exponentiation is defined as a non-commutative operation, but there are some pairs $\{a,b\}$ for which $a^b=b^a$, like for example, $\{2,4\}$. Is there any mathematical ...
184 views

### Is there a way of finding out the remaining two numbers of pythagorean triple if one of the side is given

I am solving one question related to right triangle and I have to find out the remaining two numbers of the pythagorean triple if one of the number is given. I know there can be many triples possible ,...
51 views

### Finding modular inverse by solving diophantine equation

Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this ...
386 views

### Prime Number Sieve using LCM Function

How to prove the following conjectures ? Definition : Let $b_n=b_{n-2}+\operatorname{lcm}(n-1 , b_{n-2})$ with $b_1=2$ , $b_2=2$ and $n>2$ . Let $a_n=b_{n+2}/b_n-1$ Conjectures : Every term ...
5k views

### How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...