# Questions tagged [elementary-number-theory]

Questions on divisibility, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, quadratic number fields and other related topics which may be treated in first courses on number theory. More advanced topics should instead use the number-theory or other tags.

32,773 questions
Filter by
Sorted by
Tagged with
1answer
20 views

### Prove that the number of primes that divide $B=\left \{ \sum_{i=1}^n b_ia_i^n : n\in \mathbb{N} \right\}$ is infinite

I got this interesting question which says Let $n\geq 2$ and let $a_1,a_2,\dots ,a_n$ be positive integers (not necessarily distinct) such that $(a_1,a_2,\dots ,a_n)=1$ (where $()$ represents G.C.D.) ...
0answers
67 views

### When is $14k^4 - 6k^2 + 1$ a perfect square?

Is there some sophisticated method (or maybe some easy one, though I doubt it) to show that the only solution to $m^2 = 14k^4 - 6k^2 + 1$ in positive integers is $k=1$, $m=3$? Perhaps something around ...
0answers
14 views

### Do these modifications of Pillai's conjecture equation still have (in)finitely many solutions?

So I'm aware of the Pillai's conjecture that says that $Ax^n-By^m=C$ has only finitely many solutions $(x,y,m,n)$ if $(m,n)\neq (1,1)$, when $A,B,C$ are fixed positive integers. I have the following ...
0answers
40 views

### For which $n$ there exists such an $m$?

The question is that: For which positive integer $n \geq 2$,there exists an integer $m$ such that $m^2$ is an n-digit number consisting of all the integers from $0$ to $n-1$ when presented in base $n$...
0answers
44 views

2answers
29 views

### How to figure out all possible pairs of numbers with a HCF?

The product of two numbers is $13005$ and their HCF is $17$. Find all possible pairs of numbers. I've done the first part of the question but I'm stuck on how to find all possible pairs of numbers. Is ...
0answers
24 views

### What would the answer be? [duplicate]

Both numbers are above $8,$ their HCF is $8$ and their LCM is $80.$ Find the two possible numbers. I'm very stuck on this question and was wondering if there was an easy way to answer it
0answers
24 views

### Do we have that $x$ divides $cb$ with $x,b,c\in \mathbb{Z}$ implies $\gcd(x,b)>1$ [duplicate]

I am trying to prove that the set of zero divisors of the ring $\mathbb{Z}/_{b\mathbb{Z}}$ is equal to $\{[x] \in \mathbb{Z}/_{b\mathbb{Z}}: \gcd(x,b)>1\}$. Therefore I started with the set of ...
0answers
38 views

### Maximum value of $\text{lcm}(n_1,n_2,…,n_k)$ given $n_1+…+n_k=X$

Find the maximum value of $\text{lcm}(n_1,n_2,...,n_k)$ given $n_1+...+n_k=X\in\mathbb{Z^+}$,where $n_1,...,n_k$ and $k$ are to be determined. I came across this as a lemma while solving a group ...
2answers
72 views

### An interesting identity regarding partitions of $m$ into powers of two

This question appeared in an exam I was giving- Suppose we have $n$ balls and we place them in a sequence of bins as follows. At least one ball is put into the first bin, and each successive bin has ...
3answers
84 views

### Comparing numbers of the form $c+\sqrt{b}$ (eg, $3+3\sqrt{3}$ and $4+2\sqrt{5}$) without a calculator

It is easy to compare to numbers of the form $a\sqrt{b}$, simply by comparing their squares, for example $3\sqrt{3}$ and $2\sqrt{5}$. But what if we have $a=3+3\sqrt{3}$ and $b=4+2\sqrt{5}$ for ...
1answer
64 views

### A Number Theoretic Game

I got this question in an exam I was giving- Alice and Bob are playing a game. There are $n$ coins laid out on a circular table, at positions marked from $1$ to $n$. In each round, Alice picks a list ...
0answers
64 views

### If t is a quadratic residue mod p, how can I efficiently solve the equation $x^2=t \pmod {p}$? [duplicate]

I know that if $({t\over p})=1$, then $t$ is a quadratic residue, which means that $x^2 \equiv t$ mod p has solutions. So is there any skills or methods that I can use to solve the equation given a ...
1answer
100 views

4answers
64 views

### Why does Euclid's lemma have the requirement of coprimes?

I was reading the general form of Euclid's lemma which states: If $a \mid bc$ and $a$ is relatively prime to $b$ then $a \mid c$ I don't really understand why the "relative prime" ...
1answer
41 views

### Testing membership for perfect square number

Is it sufficient to test that if a positive integer $n$ ends in $0, 1, 4, 5, 6, 9$, and that $n \equiv 0, 1 \bmod 4$ then $n$ is a perfect square? The numbers $0, 1, 4, 5, 6, 9$ I got from the ...
1answer
51 views

### Showing $\mathbb{Z}_p$ is a ring [duplicate]

In $\textit{A Classical Introduction to Modern Number Theory}$, the authors define $\mathbb{Z}_p$ as a set where $p$ is a prime number and $a,b$ form the rational number $a/b$ such that $p\nmid b$. ...
1answer
41 views

### Prove the equation if $b$ is a prime [duplicate]

When $b$ is prime and $a>0$ is any integer: $$(1/a)\pmod b \equiv a^{b-2}\pmod b$$ Can somebody explain me how this equation holds true in number theory. Someone told me that it can be proven ...
1answer
79 views

0answers
57 views

### For the eqn. $ab +bc +ca = y^n$, where a,b,c are +ve consecutive numbers, there exists no integral solutions for y when n>1? [closed]

For the eqn. $ab +bc +ca = y^n$, where a,b,c are +ve consecutive numbers, there exists no integral solutions for $y$ when $n>1$.If we choose any one of $a,b,c$ as $0$ then we will have a square, ...
0answers
40 views

### Help with data for Number of primes < n^2 [closed]

Has anyone computed the OEIS sequence A038107, i.e. Number of primes < n^2, up to 1 billion? If so, could you share the data with me please? Or simply the π(n), i.e. the number of primes not ...
4answers
82 views

### Find positive integer $x$ such that $3x+1=2^n$

Just by computing it seems $3x+1=2^n$ is true for every other $n$ such that 2^n: 16, 64,..., which corresponds to $x=5, 21,...$. This intuitively makes sense, after all, $3x+1$ is even every time $x$ ...
2answers
88 views

### For all m there exist n s.t. both 3^i*n±2 are primes for all i<m?

For all $m$ there exist $n$ s.t. both $3^in\pm2$ are primes for all $i<m$? I came up with the following question with a game. The game says: Start with an odd number $n$ greater than 3. In each ...