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
votes
2answers
18 views

prove that a number N is divisible by $5^k$ if the last k digits are divisible by $5^k$.

prove that a number $N$ is divisible by $5^k$ if the last $k$ digits are divisible by $5^k$.
0
votes
2answers
46 views

Elegant Proof that $m | xn \implies \frac{m}{(m,n)} | x$ [duplicate]

I have a proof that shows $m | xn \implies \frac{m}{(m,n)} | x$ which leans heavily on prime factorizations. Is there a more straightforward proof? Edit With this question, I was looking for a proof ...
0
votes
0answers
13 views

Can a Multiset product, mapping the relation x intersects y draw a roadmap

Can a multiset product ( like a cartesian product on sets) plotted with the relation x intersects y, draw a road map ? I tried this once before with sets (doesn't work with angling streets), but ...
2
votes
2answers
31 views

Show that the relation $(- 1) (- 1) = 1$ is a consequence of the distributive law [duplicate]

Show that the relation $(- 1) (- 1) = 1$ is a consequence of the distributive law. This question is the first problem from 'Number Theory for Beginners" by Andre Weil. I cannot get the point from ...
1
vote
2answers
42 views

For given $ab\leq n$, do there exist $a'\geq a$ and $b'\geq b$ such that $a'b'=n$?

For example, given $a=3$, $b=3$, and $n=14$, no such $a',b'$ exists. On the other hand, for $a=3$, $b=3$, and $n=12$, we can use $a'=3$ and $b'=4$. Is there a simple formula that can help determine ...
2
votes
2answers
53 views

Remainder of $(1\cdot2\cdots102)^3$ modulo $105?$

I am having trouble in finding the remainder of $(1\cdot2\cdots102)^3\mod 105$ It is not possible to apply Wilson's Theorem here because 105 is composite. Can anybody help me?
0
votes
1answer
25 views

A different statement of the Chinese remainder theorem.

My professor gave us a statement for the "Chinese Remainder Theorem" different from that stated in David M. Burton, which say: If $n_1,\dots,n_k$ are coprime positive integers, then there exist a ...
0
votes
1answer
39 views

If $p$ is a prime, and $2p = 2 \mod 4$ then $p = 3 mod 4$

If $p$ is a prime number, and $2p = 2 \mod 4$ then $p = 3\mod 4$ Is this true? I know that of the form $2x = 2\mod4$ then my solution must by of the form $2k+1$ or $1,3 \mod 4$ but does making p ...
0
votes
3answers
60 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
88 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
51 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
70 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
36 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
30 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
35 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
65 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
145 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
61 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
29 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
49 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
195 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
95 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
545 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
93 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
23 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
31 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
46 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
51 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
86 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
27 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
57 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 [closed]

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
27 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
135 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$ [closed]

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
60 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