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.

Filter by
Sorted by
Tagged with
3 votes
2 answers
27 views

Find all odd primes $p$ such that $3p-8$ is equal to the cube of a positive integer

I recently tackled this problem from one of my country's regional competitions. My solution is as follows: Let $$3p - 8 = n^3$$ From this we know that $$p = \frac{n^3 + 8}{3}$$ It follows that $$p = \...
user avatar
0 votes
0 answers
27 views

Is there a general solution for gcd problems in for of if $\gcd(a,b) = 1$, then...? [duplicate]

I know that there are lots of questions with this format with duplicated answers: If $\gcd(a,b) = 1$, show that $\gcd(2a+b, a+2b)=1 \mbox{ or } 3$ Show that $\gcd(a + b, a^2 + b^2) = 1$ or $2$ if $\...
user avatar
0 votes
0 answers
29 views

Prove that if $gcd(a,b) = 1$, than $\gcd(a+b,a^2+ b^2)$ is either $1$ or $2$ [duplicate]

Prove that if $\gcd(a,b) = 1$, than $\gcd(a+b,a^2+ b^2)$ is either $1$ or $2$ I found a solution for this using this idea, but I do not think my argument is right. Note $$d = \gcd(a+b,a^2+ b^2)\mid a+...
user avatar
0 votes
0 answers
23 views

Finding (a,p) s.t p|(1+a+...+a^6)

Let A=1+a+a^2+...+a^6 , where a>1, p an odd prime and p|A. The goal is to show that p=7 or p=1(7) I first started by showing that a^7=1(p) : A=1+a^2+...+a^6=(1/7).(a^7-1)=0(p) => a^7=1(p) And ...
user avatar
  • 91
2 votes
0 answers
37 views

Prove that for every sufficiently large $n$, we can write the positive integer $n$ in the form $n = a_1+ a_2+...+a_{2018}$ with $: (a_i , a_j ) = 1 $

Prove that for every sufficiently large $n$, we can write the positive integer $n$ in the form $n = a_1+ a_2+...+a_{2018}$ In there $: (a_i , a_j ) = 1 $ for all $i<j$ and $a_i>2018$ for all $i$ ...
user avatar
0 votes
0 answers
14 views

Is it possible to easily calculate the resulting number if I add a random integer to all of the prime factors of a given number?

If I have an composite integer called $x$, is it possible for me to calculate what the resulting number will be if I add a random integer, denoted by $n$, to all of the factors of $x$ (without ...
user avatar
0 votes
0 answers
22 views

Show that if $n \in N$ and $a,b \in \mathbb{ Z}$ s.t. $a+b=n$, then $\overline{a}, \overline{b}$ are additive inverses in $\mathbb{ Z_n}$.

If $a+b=n$, then in modulo remainder class have $\overline{a} + \overline{b}= 0$. So, $\overline{a} = -\overline{b}$. Hence, proved. Is it this simple, or am missing something?
user avatar
  • 3,433
0 votes
0 answers
29 views

Prove that $\left \lfloor \frac{p}{q} \right \rfloor + \left \lfloor \frac{2p}{q} \right \rfloor + .. + \left \lfloor \frac{(q-1)p}{q} \right \rfloor$ [duplicate]

Let p and q be coprime natural numbers. Prove that $\left \lfloor \frac{p}{q} \right \rfloor + \left \lfloor \frac{2p}{q} \right \rfloor + ... + \left \lfloor \frac{(q-1)p}{q} \right \rfloor = \left \...
user avatar
0 votes
0 answers
15 views

Find all $x$ and $y$ $\in$ $Z$, such that $gcd(x,y) = 20$ and $lcm (x,y) = 420$ [duplicate]

This is what I tried to do, but I know it is wrong. $$\begin{cases} gcd(x,y) = 20 \\ lcm(x,y) = 420 \end{cases} $$ $$x = 20m$$ $$y = 20n$$ $$(m,n) \in \mathbb{Z}$$ $$420 = \frac{x\cdot y}{gcd(x,y)}$$ ...
user avatar
0 votes
3 answers
45 views

Find all positive integers $a$ such that: $lcm(120,a) = 360$ and $gcd(450,a)=90$

Find all positive integers $a$ such that: $lcm(120,a) = 360$ and $gcd(450,a)=90$ I started by factoring $$450 = 2\times 3\times3\times5\times5$$ and $$90 = 2 \times3\times3\times5$$ Since $gcd(450,a)=...
user avatar
0 votes
0 answers
23 views

How to think a solution for the problem like this? [duplicate]

The question: If (a/b)<(c/d) with b>0, d>0 show that (a+c)/((b+d) lies between a/b and c/d where a,b,c,d are real numbers Answer to the problem: (a/b)<(c/d) which implies ac<bd. Add ...
user avatar
-4 votes
0 answers
21 views

Show that a natural number n> 1 has no more than log2 (n) prime divisors. [closed]

a) Show that a natural number n> 1 has no more than log2 (n) prime divisors. b)Show that the odd natural number n> 1 has no more than log3 (n) prime divisors
user avatar
0 votes
0 answers
27 views

Let $m$ and $n$ be positive integers such that $m = 24n + 51$. What is the largest possible value of the greatest common divisor of $2m$ and $3n$? [duplicate]

Let $m$ and $n$ be positive integers such that $m = 24n + 51$. What is the largest possible value of the greatest common divisor of $2m$ and $3n$? I'm trying to figure out how to use the Euclidean ...
user avatar
-3 votes
0 answers
42 views

Fermat's factorization method [closed]

In the case of $p$ is a prime number and $q$ is another prime number If $pq=n$ And $n$ was known in that equation. Is Fermat's method the best known method now for finding $p$ and $q$, or is there a ...
user avatar
  • 1
5 votes
1 answer
303 views

Do three consecutive numbers of form $A^2B^3$ exist?

I (non-mathematician) asked a similar kind of question 5 days ago. Now I revisit the case in a different manner. The powerful numbers may be written in the form $A^2B^3$, where $A$ and $B$ are ...
user avatar
  • 97
0 votes
1 answer
30 views

What is the greatest possible value of the greatest common divisor of $4T_n$ and $n-1$? [duplicate]

For all positive integers $n$, the $n$th triangular number $T_n$ is defined as $T_n = 1+2+3+ \cdots + n$. What is the greatest possible value of the greatest common divisor of $4T_n$ and $n-1$? Since ...
user avatar
-1 votes
0 answers
35 views

For a given positive integer $n > 2^3$, what is the greatest common divisor of $n^3 + 3^2$ and $n + 2$? [duplicate]

For a given positive integer $n > 2^3$, what is the greatest common divisor of $n^3 + 3^2$ and $n + 2$? The solution for this was to note that $n^3+8=(n+2)(n^2-2n+4)$ from where they got that $$\...
user avatar
2 votes
1 answer
36 views

Series representation of GCD(x, y) [duplicate]

While playing around with WolframAlpha, I discovered that apparently the GCD of any integers x, y is equal to the following sum: $$ x + y - xy + 2\sum_{k = 1}^{x-1} \lfloor \frac{ky}{x}\rfloor $$ I've ...
user avatar
-2 votes
0 answers
33 views

When is $2^{n-1}n +1$ a perfect square? [duplicate]

When is $2^{n-1}n +1$ a perfect square? Letting $2^{n-1}n+1=m^2$ we have that $$2^{n-1}n=m^2-1=(m-1)(m+1)$$ Now considering the parity of the lhs $2^{n-1}n$ is even for all $n >1$ and since $n=1$ ...
user avatar
2 votes
1 answer
53 views

Multiplicative order of $2$ modulo $p$.

When calculating the multiplicative order of $2$ modulo a prime $p$ you often get $p-1$ or $\frac{p-1}{2}$ as a result, but there are cases where this does not hold, is there a general form for those ...
user avatar
0 votes
0 answers
18 views

Bounded sum of reciprocals of primes

An elementary book I'm reading shows this theorem: R(x) = $\sum_{p\le x} 1/p = \log\log x + O(1) $. Proof starts with S(x) = $\sum_{p\le x} \frac{\log p}{p} = \log n +O(1)$ and I see that R(x) = $ \...
user avatar
  • 1
-4 votes
0 answers
41 views

Prove that $\left \lfloor \frac{n + 2^0}{2^1} \right \rfloor + ... + \left \lfloor \frac{n + 2^{n-1}}{2^n} \right \rfloor = n$

Prove that for any positive integer n $\left \lfloor \frac{n + 2^0}{2^1} \right \rfloor + \left \lfloor \frac{n + 2^1}{2^2} \right \rfloor + \left \lfloor \frac{n + 2^2}{2^3} \right \rfloor + ... + \...
user avatar
-1 votes
3 answers
50 views

Is there an algorithm to simplify solutions of linear Diophantine Equations?

I will use the following equation as an example: $$3x + 5y = 47$$ We know that $gcd(3,5) = 1 | 47$ so, this equation has a solution. In order to find it, we can use the euclidean algorithm and the ...
user avatar
1 vote
0 answers
32 views

Arbitrary long consecutive numbers not possessing the property $P$

I just wonder that by defining the positive integer $n$ that possesses the property $P$ to be the number that possesses $P$. For example, if $n$ possessing $P$ means that $n=x^2+y^2+b^k$ for fixed ...
user avatar
-1 votes
0 answers
40 views

What is the fact Extended Euclidean Algorithm is based on? [duplicate]

I've started to wonder about something that should be easy enough to explain for one knowing the topic well enough, but I'm unable to derive that explanation. Euclidean Algorithm is based on a fact ...
user avatar
  • 177
0 votes
0 answers
17 views

A special solution for a linear Diophantine equation in 4 variables

Suppose a,b,c,d are (collectively) coprime integers. Show that there are integers x,y,z,u such that ax+by+cz+du=1 and xu-yz=0 (the determinant of the 2x2 integral matrix [x y/ z u]). Equivalently: ...
user avatar
-3 votes
0 answers
44 views

How to solve $f(x):{{x}^{7}}-2{{x}^{6}}-7{{x}^{5}}+x+2=0\equiv (\,\bmod \,5)$? [closed]

$f(x):{{x}^{7}}-2{{x}^{6}}-7{{x}^{5}}+x+2=0\equiv (\,\bmod \,5)$. I have no idea to tackle the congruences with such a big powers. Please help me out.
user avatar
3 votes
2 answers
146 views

A number theory question that is probably wrong

Prove that $a^3-b^3 = 2011$ has no integer solutions. I think the question is wrong as $a^3-b^3 = 2011$ $(a-b)(a^2+ab+b^2) = 2011$ As $2011$ is prime so the only factors $2011$ has are $1$ and $2011$ ...
user avatar
0 votes
0 answers
27 views

How to simplify the expression for Dirichlet inverse of $\varphi$ further?

$\varphi$ : Euler totient function $\mu$: M$\ddot{o}$bius function $I =\chi_{\{1\}}$ $N\in\Bbb{K}^{\Bbb{N}}$ : $N(n)=n$ $u $ : unit function i.e $u(\Bbb{N}) =\{1\}$ We know $\varphi(n) =\sum_{d|n}\mu(...
user avatar
  • 4,216
-2 votes
1 answer
87 views

Condition for a prime to divide $a^2+ab+b^2$. [closed]

Any hints for proving that if $p$ is a prime of the form $3k+2$ and $p \mid a^2+ab+b^2$ then $p \mid a$ and $p \mid b$?
user avatar
0 votes
0 answers
39 views

A Number Theory problem on AoPS Alcumus

For positive integer $n$ such that $n < 10000$, the number $n+2005$ has exactly 21 positive factors. What is the sum of all the possible values of $n$? Given that $n + 2005$ has $21$ positive ...
user avatar
0 votes
0 answers
26 views

Bezout Lemma in a PID [duplicate]

The Bezout Lemma in the integers states that For any $a, b \in\mathbb Z$, let $g = \gcd(a, b)$, There exists $x, y$ such that $ax+by = g$. This can be generalized to a commutative ring that is a ...
user avatar
2 votes
0 answers
46 views

Proof regarding principal factors of the discriminant in $\mathbb{Q}(\sqrt{d})$

So I understand there are (up to $\pm$) exactly two primitive (no rational integer factors) elements $\alpha_1 ,\alpha_2 \in \mathcal{O}_K$ such that the fundamental unit $\varepsilon$ of $K=\mathbb{Q}...
user avatar
  • 21
-1 votes
1 answer
36 views

Problem regarding quadratic recidues that I cannot solve [duplicate]

The problem is as follows: Let $p$ be a prime and assume that $p=1$ mod 5. Let $c\in\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$ be an element of order 5 and let $g=2(c+c^{-1})+1$ Show that $g^2=5$ ...
user avatar
  • 15
0 votes
2 answers
86 views

I want to Find what are the last three digits of $25^{63} \cdot 63^{25}$

I have the solution on how to solve it but I don't know what does mod(1000) means here, please help me
user avatar
7 votes
2 answers
1k views

Longest geometric progression of primes

There are arbitrarily long arithmetic progressions of primes e.g. $5, 11, 17, 23, 29$ for a $5$-length progression, but no (infinite) arithmetic sequence of primes with common difference $d\neq 0$, as ...
user avatar
  • 3,528
2 votes
1 answer
59 views

For every prime p there is a sum of squares congruent to -1 mod p [duplicate]

For every prime $p$, there exists $a,b \in \mathbb{Z}$ such that $p\mid a^2+b^2+1$ For context, this question shows up as a statement on a hint to showing that every positive integer is a sum of 4 ...
user avatar
0 votes
0 answers
30 views

show that there are arbitrarily long sequences of consecutive positive integers which are not sums of two squares [duplicate]

Let $p_1, p_2, . . . , p_k$ be different prime numbers. By the Chinese Remainder theorem, show that for each $k ∈ N$ there exists an integer n such that $p_1 |n+1; p_2 |n+2; ...; p_k |n+k$ but $p^2_k$ ...
user avatar
  • 39
0 votes
4 answers
96 views

Show that there are infinitely many solutions $x, y, z \in\mathbb N$ of the following equation $x^2 + y^3 = z^7.$ [closed]

Show that there are infinitely many solutions $x, y, z \in\mathbb N$ of the following equation $x^2 + y^{3} = z^7$. I am thinking about using proof by infinite descent, but I am not too sure how to ...
user avatar
  • 39
0 votes
0 answers
43 views

Give an equation for a line that contains no lattice points.

Give an equation for a line that contains no lattice points. Explain how you know it contains no lattice points. This problem is taken from section 5.1 exercise Q.9. of book: Number theory, by: James ...
user avatar
  • 3,433
0 votes
1 answer
30 views

Integers starting at 1 and ending at 5 that are divisible by 9.

I want to find the integers starting at 1 and ending at 5 that are divisible by 9. An integer is a multiple of 9 if: $$n = a_k a_{k-1} \cdots a_1 a_0 \Rightarrow a_k+a_{k-1}+\cdots a_0 \equiv 0 \pmod{...
user avatar
0 votes
0 answers
45 views

Calculate a non trivial divider of a number

given that: $1683411^{2}=4\mod(2195689)$ calculate a non trivial divider of $2195689$ (without using calculator) My try: $$ 1683411^{2}=4\,mod(2195689) \\~\\ 1683411^{2}-4=0\,mod(2195689) \\~\\ (...
user avatar
  • 341
4 votes
3 answers
158 views

Find all $4$ digit numbers such that sum of digits is $11$.

Find all $4$ digit numbers such that sum of digits is $11$. \begin{cases} x_1+x_2+x_3+x_4=11\\ 1\leq x_1{\leq 9}\\ 0\leq x_2{\leq 9}\\0\leq x_3{\leq 9}\\ 0\leq x_4{\leq 9}\end{cases}. Using stars and ...
user avatar
1 vote
1 answer
219 views

Three consecutive powerful integers do not exist

I (who is not a professional mathematician), ended up in the following on which I would like to have your comment, because this is overly simple solution. I know this certainly should not be easy and ...
user avatar
  • 97
1 vote
0 answers
47 views

Pell-Type Equation: show that the solutions $x,y$ are such that $\frac{x}{y}$ is a convergent

Prove that for any solution of the equation $x^2 − 14y^2 = 2$, in positive integers $x, y$ the value $\frac{x}{y}$ is a convergent of $\sqrt{14}$ I am not too sure where to start, I have the continued ...
user avatar
  • 39
2 votes
3 answers
106 views

If $ab+1 = r^2$ for $a,b,r \in \mathbb{N},$ how to show that $\gcd(2a(r+b)+1,2b(r+a)+1) = 1?$

Let $a<b$ be positive integers such that $ab+1 = r^2$ for some $r \in \mathbb{N}.$ If $m_1 = 2a(r+b)+1$ and $m_2 = 2b(r+a)+1.$ I want to find the possible values of $\gcd(m_1,m_2).$ I had taken ...
user avatar
0 votes
0 answers
27 views

Prove that $a(a^{2}-1)$ is divisible by 6 [duplicate]

$a$ is a natural number that isn't equal to 0 My attempt: $a(a^{2}-1)$ = $a(a-1)(a+1)$ There are 2 cases here: If a = 2k: We have $2k(2k+1)(2k+1)$ because $a-1$ and $a+1$ come before and after $a$ so ...
user avatar
1 vote
1 answer
45 views

Number of functions under some conditions

let $A=\{0,1,2,\dots,8\}$ and $B=\{0,1,2,\dots\}$. How many function from $A$ to $B$ can be defined such that the following will be hold: $f(x+y \bmod{9}) = f(x)+f(y) \bmod{12}$ $f(x \cdot y \bmod{9}...
user avatar
  • 830
-3 votes
0 answers
69 views

Find all prime $p$ such that $8 p^{2}+1$ is a prime also. [closed]

I can't figure out how to even approach it, just tried some bunch of modulos and fermat's little theorem on $2^{3}$ but couldn't figure out anything.
user avatar
0 votes
1 answer
51 views

How to show the coprimality? [closed]

Let $a,b,r\in \mathbb{N}$ such that $ab+1=r^2$ and $$m_1 = 2r(a+r)-1\\ m_2=2r(b+r)-1.\\$$ I want to know the possibile values of $\gcd(m_1,m_2),~\gcd(m_1,a)$ and $\gcd(m_2,b).$ Do all of those values ...
user avatar

1
2 3 4 5
689