Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-number-theory]

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

1
vote
0answers
51 views

There cannot be more than three primes of the form $n^{n^2}-k$ for the same $k$?

I was searching for primes of the form $n^{n^2}-k$ on PARI/GP and noticed that primes of this form for same $k$ are quite rare. The probability of finding a prime of this form is $\frac {1}{n^2 \log (...
1
vote
1answer
39 views

$a^x + b^y = c^z \Rightarrow a^{x-2} + b^{y-2} = 0 $ (mod c) if $x,y,z > 2$ and $a,b,c$ are pairwise coprime?

Let $a,b,c,x,y,z$ be positive integers such that $x,y,z > 2$ and $a$,$b$,$c$ are pairwise coprime. Suppose it is given that $a^x + b^y = c^z$ (i.e $a^x + b^y \equiv 0 (\text{mod } c)$), then is it ...
4
votes
2answers
90 views

Find all positive integers $n$ and $m$ such that $(125\times2^n)-3^m=271$

Find all positive integers $n$ and $m$ such that $(125\times2^n)-3^m=271$ I have thought about this question for a long time and I can't seem to solve it. I realize that $271$ is a prime and so I'm ...
1
vote
1answer
375 views

Is this book good to learn olympiad level number theory?

I'm an undergraduate student and I would like to learn olympiad level-number theory. For what I've read, Number theory: Structures, Examples and Problems is a great book, however, I'm not sure it is a ...
1
vote
1answer
66 views

Prove that the sum $1+2+3+4+5+6+7+\ldots+n$ is never prime for $n>2$.

I'm trying to prove that the sum of consecutive integers $1+2+3+4+5+6+\ldots+n$ is never prime for all integers $n>2$. Here's what I tried. I assumed that the sum $1+2+3+4+5+\ldots+n=p$, where $p$ ...
1
vote
1answer
139 views

Does no prime exist of the form of $k^k+11$?

I tried searching for primes of the form $k^k+11$ on PARI/GP and found that no such prime exists for $k \le 10^4$. Questions: $(1)$ Is there any reason I cannot find a prime of the form $k^k+11$? ...
3
votes
3answers
459 views

Proof that $\sum_{d|m} |\mu(d)|=2^n$, where $n$ is the number of distinct prime divisors of $m$?

Given an integer $m$ such that $n$ is denoting the distinct prime divisors of $m$, is there a proof that the sum over the divisors of m of the absolute value of the Möbius function $\mu(d)$ is equal ...
-1
votes
1answer
28 views

Greatest Integer Function - solve for real $x$ [on hold]

Solve for real $x$: $[x^2]=[2x-1]$ where $[x]$ is floor/box function.
0
votes
1answer
35 views

Proof that any integer $z>1$ can be written as $2x+y$, where $x>y$

Imagine a multiple choice questionnaire with 3 choices $a, b,$ and $c$. At the end the sums of each choice are tallied. It seems it's always possible to have a tie for first, as long as the total ...
1
vote
2answers
33 views

Prove that there exists an integer greater than x such that any polynomial $f(x)$ will be strictly non-negative and get large?

Hi I am taking a number theory class and so far I have been proving modular congruences, modular arithmetic, and prime properties. There is this theorem that came up in the textbook and apparently it ...
2
votes
1answer
60 views

What is the difference between, a “square” and a “perfect-square”, number?

Is, "36", a perfect square? I know that, "4" is a perfect square. Similarly, "1","9","25", are "perfect-square"s.
1
vote
0answers
53 views

Infinitude of super happy primes

Similar to happy primes, I define super happy primes by the following process: $(1)$ Find the sum of the digits raised to the power of themselves. Ex. $13$ gives sum $ = 1^1 + 3^3 = 28$ $(2)$ If ...
-1
votes
0answers
16 views

Infinitely many $n$ such that $2^n$ ends with $n$ [duplicate]

Prove that there are infinitely many integers $n$ such that the decimal representation of $2^n$ ends with $n$.
0
votes
0answers
17 views

A discrepancy in the used general solution of linear diophantine equation in David M. Burton book.

In David Burton book "seventh edition", the general solution of linear diophantine equation is given below (in page 34): Then in page 76 after linking linear congruences with linear diophantine ...
2
votes
1answer
14 views

A difference in a formula of theorem 4.2(e) on congruence relations.

The statement of the theorem said : If $a \equiv b \pmod n$ then $ac \equiv bc \pmod n$. But I have seen it in other place as: $a \equiv b \pmod n$ then $ac \equiv bc \pmod {nc}$. Are they ...
6
votes
1answer
46 views

Is there a maximum number of consecutive sexy prime pair sums that are all divisible by $10$?

I was finding the sums of pairs of sexy primes (prime numbers that differ by 6) and noticed that there are a lot of pairs who's sum is divisible by $10$. Ex. $(7, 13)$ as $7+13=20$ and $20$ is ...
0
votes
1answer
27 views

For every $n\in\mathbb{N}$ , the equation $\varphi(x)=n$ has a finite number of solutions [duplicate]

How can I prove that for every $n\in\mathbb{N}$ , the equation $\varphi(x)=n$ has a finite number of solutions ? $\varphi(n)$ denotes the totient function.
0
votes
2answers
70 views

Proving $1+\sqrt2+\sqrt3$ is irrational [duplicate]

How can I prove that $1+\sqrt2+\sqrt3$ is an irrational number, without proving first $\sqrt2$ and $\sqrt3$ are irrational numbers? Please give some hints or suggestion to proceed with this proof. ...
1
vote
0answers
27 views

Why is that minimum positive element in the ideals of linear combinations is the GCD of it's factors?

Why is that the smallest positive element in the ideals of the form $a_1\mathbb Z + a_2\mathbb Z+...$ is the greatest common divisor of the coefficients $a_1, a_2...$? I have seen a proof of that ...
9
votes
1answer
194 views

Find this seven digit phone number under certain conditions

This was a problem that was recently asked at a competition I attended: I have a seven-digit phone number that satisfies the following property: taking the last four digits and placing them in the ...
6
votes
2answers
92 views

Is there any $k$ , for which we can prove that $n^n+k$ is never prime?

Is there any positive integer $k$, such that we can prove that $n^n+k$ is not prime for any positive integer $n$ ? $$n^n+1805$$ has a prime factor not exceeding $43$ up to $n=1805$. However, for the ...
3
votes
1answer
535 views

Does anyone recognize the function from this picture?

I was playing with the exterior algebra, and stumbled on this interesting function from $\Bbb N^2 \to \Bbb N$, which I'll call $f(x,y)$. This is plotted from $1 \leq x,y \leq 100$: In this picture, ...
0
votes
0answers
9 views

Why reconciling this condition is setting $d_{k} = 0$?

Why if $b$ divides $d_{k}$ and $|d_{k}| < b$, this leads to $d_{k} = 0$? Could anyone explain this for me please?
3
votes
2answers
80 views

If $a^{m}+1|a^{n}+1$ then prove that m|n.

Actually I know a similar proof which is, $a^{m}-1|a^{n}-1 \iff a|n$ But I can't prove this. I also need some examples of the question. Can't seem to find any correlation between the two proofs. I ...
3
votes
1answer
709 views

Ulam spiral and triangular numbers

Is there any explanation for the twister-like pattern build by triangular numbers $$\Delta_n = \frac{n\cdot(n+1)}{2}$$ in the Ulam Spiral? Here for $1,\ldots,100$: Here's a picture with many more ...
1
vote
0answers
21 views

Algorithm expressing a fraction as a sum of unit fractions

I am looking for an algorithm to express some fraction $\frac{a}{b}$, with $a,b \in \mathbb{Z}$, as a sum of unit fractions, like: $$\frac{a}{b} = \frac{1}{w_1} \pm \frac{1}{w_2} \pm \frac{1}{w_3} \...
0
votes
0answers
224 views

New primality test for $2m^n+1$ (where $m$ is prime)? [on hold]

If $N=2.m^n+1$ (where $m$ is prime) you can prove if $N$ is prime or not by these two steps: Step (1) if $a^{2.m^{n-1}}=L \mod(N)$ (which is $L\neq1$ ) Step (2) $L^{m}=1 \mod(N)$ So N is prime. ...
0
votes
2answers
88 views

Prove for every $m, n$, $(m^2 - n^2, 2mn, m^2 + n^2)$ can make pythagorean triple

I tried researching more about this because it seems to be a common topic, but I don't know how to approach this problem. Do I have to somehow arrange those 3 terms into $a^2 + b^2 = c^2$?
1
vote
2answers
52 views

Please explain the proof of the validity of the Cauchy convergence criterion for real number sequences.

My question pertains to BBFSK, Vol I, Pages 143 and 144. The following appears in the context of developing the real numbers as limits of sequences of rational numbers. It is also easy to prove ...
0
votes
1answer
52 views
+50

Can we construct a multiple of any number by repeating another arbitrary number twice?

Extension of this question: given a desired integer (non-necessarily prime) factor $f$, can we solve for some $n$ such that any arbitrary $n$ digit number repeated twice is a multiple of $f$? ...
6
votes
2answers
247 views

Prove there is only one solution to the Diophantine equation $p^n - p = q^m - q$ where $p$ and $q$ are odd primes $p\gt q$

Consider numbers of the form $p^n - p$ where $p>2$ is a prime and $n>1 \in \mathbb{Z}$. How many of these have a unique representation? $2184$ can be written in this form $2$ ways, $3^7-3, 13^3-...
0
votes
0answers
29 views

Children in Stern-Brocot tree

Here it says that if we have a fraction $$[a_0;a_1,...,a_k]$$ in the Stern-Brocot tree, then its children are $$[a_0;a_1,...,a_k+1] \text{ and } [a_0;a_1,...,a_{k}-1, 2].$$ Also, one of them is left ...
12
votes
5answers
3k views

Prove that all even integers $n \neq 2^k$ are expressible as a sum of consecutive positive integers

How do I prove that any even integer $n \neq 2^k$ is expressible as a sum of positive consecutive integers (more than 2 positive consecutive integer)? For example: ...
0
votes
2answers
45 views

How to prove that $ n < n! - 1 $ for $n > 2.$? [on hold]

How to prove that $ n < n! - 1 $ for $n > 2.$? I have tried it by induction but I got stucked in the induction step in proving $ n +1< (n + 1)! - 1 $ for $n + 1> 2$. Could anyone help ...
1
vote
2answers
43 views

Floor function summation[difficult]

The question is to find the value of — $$\sum_{r=1}^{502} \Big \lfloor \frac{305r}{503}\Big \rfloor$$ The answer is pretty big, so I don't think trial and error will work here. I seriously can't ...
3
votes
2answers
32 views

How to solve a system of diophantine equation and gcd

For example I want to solve this system $$ \left\{ \begin{array}{c} 5x-3y=24 \\ \gcd(x,y)=8 \\ \end{array} \right. $$ I found that $(x,y)=(3k+6,5k+2)$ but I think I need to find $k$ so that $\gcd(...
0
votes
1answer
48 views

Why $p \leq n$ implies $p | n!$?

Why $p \leq n$ implies $p | n!$ ? if $n > 2,$ Why $p \leq n$ implies $p | n!$ ? I was trying to solve: prove that if $n > 2,$ then there exists a prime $p$ satisfying $n < p < n!.$ And ...
3
votes
0answers
85 views

Is $6379$ the only prime $p \gt 2$ where $(p+1)!+1$ is prime? [on hold]

I searched for primes of the form $(p+1)!+1$, where p is prime for a range of $2\lt p \le10^4$ on PARI/GP and found that $p=6379$ is the only prime in this range. Questions: $(1)$ Is $6379$ the ...
0
votes
1answer
26 views

Solutions to simple Diophantine Equation [on hold]

Find all solutions to the equation $3^x - 3^y = 3$ where $x, y$ are positive integers (or show there are none). I know there are no solutions to this, so I know I can set up the proof for 2 cases: $x ...
0
votes
1answer
61 views

Are there any special names given to the structures $\left<\mathbb{N}_0,+,\times\right>$ and $\left<\mathbb{N},+,\times\right>$?

Following my grade school education, I will call the set $\mathbb{N}_0\equiv\left\{0,1,2,\dots\right\}$ the whole numbers, and the set $\mathbb{N}\equiv\left\{1,2,3,\dots\right\}$ the natural numbers. ...
1
vote
3answers
81 views

Proof that for coprime $a$ and $b$, there is a prime of the form $an+b$

Suppose , $a$ and $b$ are coprime positive integers. Is there an easy way to show that $an+b$ is prime for some positive integer $n$ ? Dirichlet's theorem states that there are infinite many ...
2
votes
5answers
236 views

Solving $x^{45} \equiv 7 \mod 113$

Pretty much as in the title, though a more general answer would also be nice. . I thought you could find in inverse of $45$ in mod $113$, then take the equation to that power. In this situation that ...
0
votes
1answer
42 views

Number system construction book recommendation

I am coming to the end of 'a logical introduction to proof' by Cunningham and was thinking of continuing with some foundational topics. As such i think i may try the following: Set Theory: A First ...
1
vote
1answer
56 views

Knowing that $a+b\equiv 1 \pmod{7^{n+1}}$ show that $a^7+b^7\equiv 1 \pmod{7^{n+2}}$

Knowing that $a,b$ are prime integers and $a+b\equiv 1 \pmod{7^{n+1}}$ show that $a^7+b^7\equiv 1 \pmod{7^{n+2}}$ I used $a^7+b^7=(a+b)(a^6-a^5b+a^4b^2-a^3b^3+a^2b^4-ab^5+b^6)$ and tried to show that ...
0
votes
3answers
57 views

Question about LCM between $n^2+1$ and $n(n^2-1)$ [on hold]

If $n$ natural number $n≥2$, then find $LCM$ and $GCD$ of $n^2+1$ and $n(n^2-1)$ I don't have any ideas to approach plz help me
46
votes
7answers
7k views

Polynomial division: Is this trick obvious?

The following question was asked on a high school test, where the students were given a few minutes per question, at most: Given that, $$P(x)=x^{104}+x^{93}+x^{82}+x^{71}+1$$ and, $$Q(x)=x^4+...
2
votes
1answer
24 views

Floor function equation with $n$ solutions

The question is — The equation $\lfloor ax \rfloor = x$ has exactly $n$ distinct solutions, given that $n \in \mathbb{N}, n \geqslant 2$ and $a \in \mathbb{R}, a > 1$. Find the range of $a$. My ...
4
votes
3answers
92 views

Prime number and square problem

How many pairs of natural numbers, not bigger than 100, are such that difference between that pair is a prime number, and their product is a square of a natural number. My attempt: I tried writing ...
1
vote
3answers
83 views

Find the smallest $n$ such that the $n$-th prime $p_n \equiv 330 \mod n $.

Find the smallest $n > 1$ such that the $n$-th prime $p_n \equiv 330 \mod n $. I was investigating the remainders when the $n$-th prime is divided by $n$. For every positive integer $a < 330$, ...
-2
votes
5answers
31 views

Give a Prove that the only consecutive no nulls integers numbers a, b, c [on hold]

Give a Prove that the only consecutive no nulls integers numbers a, b, c that satisfy the equality $a² + b² = c²$. are 3, 4, 5. -Thank you in advance.