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.

0
votes
0answers
27 views

Solving a congruence, tricky implication

We want to prove that $$243x \equiv 1 \mod 2018 \implies x^{403} \equiv 3 \mod 2018$$ My try : Assume that $243x \equiv 1 \mod 2018$ We have $x^{2016} \equiv 1 \mod 2018$ (by Fermat ($1009$ is ...
2
votes
1answer
57 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 ...
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$ ...
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
votes
1answer
29 views

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

Solve for real $x$: $[x^2]=[2x-1]$ where $[x]$ is floor/box function.
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
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$? ...
-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$.
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 ...
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 ...
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.
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 ...
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
536 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?
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 ...
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 ...
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
30 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 ...
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 ...
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
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(...
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 ...
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 ...
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
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
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
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.
1
vote
1answer
26 views

Assumptions in Artin's primitive root conjecture

I'm having a little trouble, understanding the necessity of the assumptions in Artin's Conjecture. Artin's primitive root conjecture states, that: for any $$a\in \mathbb{Z}\setminus \{-1\}$$ and $$...
0
votes
1answer
30 views

Find all prime $p$ such that there exists integers $m$ and $n$ satisfying $p=m^2+n^2$ and $p$ divides $m^3+n^3+8mn$

I need to find all prime $p$ such that there exists integers $m$ and $n$ satisfying $p=m^2+n^2$ and $p$ divides $m^3+n^3+8mn$. This is a tough question in my opinion as I have been trying for some ...
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 ...
7
votes
1answer
127 views

Prove that $2^{30}$ has at least two repeated digits.

Prove that $2^{30}$ has at least two repeated digits. I assume that the question is asking me to prove that $2^{30}$ has at least one digit that appears twice. Correct me if I'm wrong. (I later ...
0
votes
1answer
48 views

Problems : equation prime numbers : $p^2+1=q^2+r^2$ [on hold]

Let $p,q$ and $r$ be prime numbers 1) Find four solutions $(p,q,r)\in N^3$ for the equation: $p^2+1=q^2+r^2$ 2) Can you generalize? Justify your answer.
1
vote
3answers
59 views

Primes number $n,n+2,n+6,n+8,n+12,n+14$

Find all natural number $n$ such that all the following numbers are primes : $$n,\;\; n+2,\;\;n+6,\;\;n+8,\;\;n+12,\;\;n+14$$ are all prime numbers
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
1answer
33 views

Why $\phi(n)\leq n(1-\frac{1}{p})$

could you tell me why $\phi(n)\leq n\left(1-\frac{1}{p}\right)$ If $\frac{\phi(n)}{n}=\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)\cdots\left(1-\frac{1}{p_{k}}\right)$
-1
votes
1answer
27 views

How to prove that an intger is either of the form $2^k$ or a sum of consecutive integers. [duplicate]

I would like to show that an integer $p$ is either sum of consecutive integers or is of the form $2^k$ $k\in \Bbb N$. I know that $p$ is the sum of consecutive integers if and only if $$p =\frac{m(...
1
vote
2answers
27 views

Find all integer solutions to hyperbola.

The question is find all integer solutions to $6xy+4x-9y-7=0$ Now I did trial and error and found $(1,-1)$ to be an integer solution. This question is in my summer math homework. We have not been ...
0
votes
5answers
38 views

fraction $\frac{21n+4}{14n+3}$ , $n\in N$

Prove tat for every natural number $n$ the fraction $\frac{21n+4}{14n+3}$ is irreducible How can I beginning in this problems I don't have any ideas to approach it
-4
votes
0answers
57 views

Is 29 the only prime of the form p^p+2 [duplicate]

searched for primes of the form p^p+2 but the only one I have found is 29
2
votes
4answers
101 views

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333…3.(100 3's)

Find the least whole number only consisting of the digit 1 such that it is divisible by 3333...3.(100 3's). My approach: we see that 111 is divisible by 3. Hence 100 3's would divide 300 1's. Is my ...
-3
votes
2answers
60 views

Find all prime numbers $P$ such that the sum of all divisors of $P^{4}$ is complete square [on hold]

Question : Find all prime number $P$ such that the sum of all divisors of $P^{4}$ is complete square I find this problems in book and I need solution or idea to approach Please help me ...