Stack Exchange Network

Stack Exchange network consists of 174 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
1answer
31 views

How to solve this modular congruence?

I have a system of two modular congruences: $x \equiv k \bmod{m}$ and $x \equiv 0 \bmod{23}$ Where $k$ and $m$ are known quantities and I want to find $x$. I'm at a loss as to whether or not there'...
1
vote
2answers
52 views

Solutions to $x^2+x-1\equiv 0$ mod $p$

The problem is to find all prime number p such that the above congruence has solutions. I started this problem by rearranging the equation such that: $$ x(x+1)\equiv 1 \pmod{p} $$ The hint given was ...
2
votes
2answers
54 views

Is the equation $3x+3=0$ solvable in Z6?

I start off by adding 3 to each side of the equation because 3 is the additive inverse of itself in Z6. $3x+3+3=0$ Then, because 3+3=0 in Z6, I have: $3x=3$ Next I need to find the multiplicative ...
-1
votes
1answer
36 views

If $l=lcm(n,m)$ and $x$ is a common multiple of $n$ and $m$, prove $l|x$ using quotient remainder thm

lcm is the least common multiple and n,m are positive integers. Do I somehow incorporate the fact that $n|x$ and $m|x$?
0
votes
1answer
21 views

If $1<a<b$, when is $a^b>b^a$? [duplicate]

Given $a,b\in \mathbb{N}$ where $1<a<b$, when is it so that $a^b > b^a$? I feel like this should be a known result but I cannot for the life of me find it.
0
votes
0answers
19 views

How to: $f(x)$ congruent to $a \pmod{b^n}$

I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class. The specific question is ...
0
votes
2answers
36 views

Infinitely many consecutive primes with difference greater than 2. [on hold]

Let $p_k$ be the $k$-th prime number. Show that there are infinitely many $k$ such that $$p_{k+1} − p_k > 2$$. Suppose If this is not true then won't that contradict the twin-prime conjecture?
1
vote
2answers
23 views

About The Sum of Positive Divisors of $n$

The question says: Find the smallest positive integer $n$ so that $\sigma(x)=n$ has no solution, exactly two solutions, exactly three solutions. I could not come up with a good way to solve this ...
1
vote
1answer
20 views

Congruence involving CRT

I was working on a problem, I arrived at the point at which I have to find $17^{{{17}^{17}}^{17}} \pmod {25}$ My attempt: $$ 17^{{{17}^{17}}^{17}}\equiv 17^{{{{17}^{17}}^{17}} \pmod{\phi(25)}} \pmod {...
0
votes
0answers
16 views

$\operatorname{Li}(x)$ vs $x/\log(x)$ vs ${\pi}(x)$ - terminology in PNT for arithmetic progressions

Wikipedia describes the prime number theorem for arithmetic progressions in the following terms: $\pi_{n,a}(x)\sim \frac{1}{\varphi(n)}\operatorname{Li}(x)$ Other sources use $\frac{x}{\log(x)}$ in ...
2
votes
2answers
44 views

Proving polynomial over Q is irreducible

Prove that if $a$ and $b$ are odd then the polynomial $$x^3+ax+b$$is irreducible over $\mathbb{Q}$ I would be very much thankful if someone could help me with this one.
1
vote
0answers
26 views

Using least common multiple to prove there exists a prime between $2x$ and $3x$

Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots, x\}$. Hanson showed that $\text{lcm}(x) < 3^x$ I'm wondering if the following argument is valid for showing that there is ...
0
votes
2answers
27 views

If $c | b(x, y, z,…)$, does $c | b$?

If $c$ divides something like $bxcd + bhdwou + bn$, does $ c | b$? I'm confused because say that's true. Then let $c = 5$ and $b = 6$. Then $c | b(10)$, but $5$ does not divide $6$. So it this ...
2
votes
2answers
86 views

Does there exist solutions to the diophantine equation $x^3-y^3 = n$? If so, what conditions on $n$ are necessary?

Does there exist solutions to the diophantine equation $x^3-y^3 = n$? If so, what conditions must be placed upon $n$ for solutions to exist?
0
votes
0answers
23 views

Probability that a natural number is a k-th power

I would like to determine the probability that a natural number is a k-th power. It is quite straightforward to see that the probability for a natural number less than N to be a I-that power is $$N^{1/...
1
vote
4answers
30 views

Prove that $a + 2b \equiv 0 \pmod{3}$ if and only if $a \equiv b\pmod{3}$.

I need to prove that $a + 2b \equiv 0\pmod{3}$ if and only if $a \equiv b \pmod{3}$. I know that you need to show both cases but my professor said that we weren't supposed to use one to solve the ...
1
vote
3answers
42 views

Why is $5$ the remainder of $5 \over 13$?

I don't understand why the remainder of $5 \over 13$ is $5$. I know that the DA tells us that $5 = 0(13) + r$ so the remainder has to be $5$ based on this, but I'm a little unsure of why/how it works
1
vote
2answers
25 views

The totient of a factor of a number divides the totient of the number.

Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?
0
votes
0answers
11 views

Formula for number of multiples of $n$ in a given interval [a,b]

Given an interval $[a,b]$ and $n$, find the number of multiples of $n$ in the interval. ($a,b,n$ are natural numbers) Examples : 1) There are $2$ multiples of $3$ in the interval $[0,3]$ 2) There ...
0
votes
4answers
24 views

Example of an assertion which is not true for any positive integer, yet for which the induction step holds.

Give an example of an assertion which is not true for any positive integer, yet for which the induction step holds. First of all, definition. In inductive step, we suppose that $P(k)$ is true ...
1
vote
3answers
73 views

Find all positive integers $a$ and $b$ such that $(1 + a)(8 + b)(a + b) = 27ab$.

Here's the problem I'm having difficulties with: Find all positive integers $a$ and $b$ such that $$(1 + a)(8 + b)(a + b) = 27ab\,.$$ Does anyone have an idea how to do this? Any detailed solution ...
1
vote
0answers
19 views

On the number of multiplicative sub-monoids of integers mod $n$

Let $n \geq 2$ be given. Is there a formula describing the number of multiplicative closed subsets of the ring $\mathbb{Z}_n$ ?
5
votes
1answer
127 views

A proof that $\sqrt{2}$ is not a rational number.

Is this proof correct? Suppose that $\sqrt{2}=\frac{a}{b}$, where $a,b \in \mathbb{N}$ and $a$ is as small as possible. Then $\sqrt{2}b=a$ which means $2b=\sqrt{2} a$. So we rewrite $\sqrt{2}=\frac{a}...
0
votes
0answers
27 views

How can I find the exponent $n$ efficiently?

Denote $$z=(2^{19}-1)\cdot10^6+2^{18}-1$$ $$a=ord_2(z)$$ $$b=ord_{10}(z)$$ The object is to find a positive integer of the form $$n=ka+19$$ with positive integer $k$ such that $$m=f(n)=\lceil(n-1)\...
4
votes
1answer
40 views

Find $5$ numbers where the sum of all pairs gives the results $110, 112, 113, 114, 115, 116, 117, 118, 120, 121$

Find $5$ numbers where the sum of the pairs gives the results $110, 112, 113, 114, 115, 116, 117, 118, 120, 121$ I have been trying on this question for some time and it seems easy at first glance, ...
2
votes
1answer
51 views

Integer equations

I have $2$ following problems. Find integer roots of $$\begin{align} &1)~\frac{x+y}{x^2-xy+y^2}=\frac3z \\ &2)~x^3y^3-4xy^3+y^2+x^2-2y-3=0 \end{align}$$ I have no idea to solve them. I try ...
2
votes
2answers
48 views

Let $r$ be primitive root mod $p$. When $x$ goes from $1$ to $p-1$, then $r^x$ (mod $p$) goes through all the numbers $1,\dots,p-1$ in some order

I'm trying to understand this situation. Why do the powers of primitive roots smaller than $p-1$ generate all DISTINCT elements in $\mathbb{Z}_p$? I am aware about what Fermat's little theorem states ...
1
vote
1answer
26 views

Miller’s test for the base $b$

Definition: Let $n$ be an integer with $n > 2$ and $n − 1 = 2^st$, where $s$ is a non-negative integer and $t$ is an odd positive integer. We say that $n$ passes Miller’s test for the base $b$ if ...
1
vote
1answer
53 views

Unable to solve this exponential equation - Diffie-Hellman key exchange

By looking at it, I can deduce that $a = 6$, and $b = 5$, but how do I can solve for $a$ and $b$ without guessing? $$2^a = 11b + 9$$
2
votes
2answers
60 views

Number Theory: Prove that $\gcd(a,b) \le \sqrt{a+b}$

For positive integers $a$ and $b$, we know $\dfrac{a+1}{b} + \dfrac{b+1}{a}$ is also a positive integer. Prove that $\gcd(a,b) \le \sqrt{a+b}$. Using Bézout's lemma, we know that $\gcd(a, b) = sa + ...
2
votes
1answer
32 views

Conjecture: if $a$, $b$ and $c$ have no common factors, dividing each of them by their sum yields at least one irreducible fraction

Let $a$, $b$ and $c$ be $3$ integers with no common factors. I conjecture that at least one of the three fractions: $$\frac{a}{a+b+c},\quad\frac{b}{a+b+c},\quad\frac{c}{a+b+c}$$ is ...
3
votes
1answer
68 views

Solving the Diophantine equation $y^3 = 4x^2+4x+ 5$ for $x,y \in \mathbb{Z}$

I want to solve the Diophantine equation $y^3 = 4x^2+4x+ 5$ for $x,y \in \mathbb{Z}$. The right hand side factors as $(2x+1-2i)(2x+1+2i)$. Am I right that such a factorization can be found using the ...
0
votes
1answer
14 views

Remainders and divisors [duplicate]

Two integers $a,b$ have the same remainder when divided by $x$. What is $x$ in terms of $a$ and $b$? Is there a way to find the answer without using modular arithmetic?
0
votes
3answers
43 views

Showing that the Diophantine equation $3x^2 + 6y^6 + 1 = 8xy^3$ has no solutions $x,y \in \mathbb{Q}$

I want to show that the Diophantine equation $3x^2 + 6y^6 + 1 = 8xy^3$ has no solutions $x,y \in \mathbb{Q}$. I tried factoring, but didn't manage (but I'm not good at factoring). Then I tried ...
1
vote
2answers
53 views

Solving the Diophantine equation $y^2 = x^4+x+ 2$ for $x,y \in \mathbb{Z}$

I want to solve the Diophantine equation $y^2 = x^4+x+ 2$ for $x,y \in \mathbb{Z}$. I already found 4 solutions: $(x,y) = (1,\pm2)$ and $(x,y)=(-2,\pm4)$. It can probably be solved using some ...
4
votes
6answers
61 views

Prove that if $p$ is prime and $p\le$ $n$ then p does not divide $n!+1$.

Prove that if $p$ is prime and $p\le n$ then $p$ does not divide $n!+1$. I know that in this case since $p$ divides $n!$, then it does not divide $n!+1$ but I am not sure how to show this.
5
votes
1answer
69 views

Prove that for all $n$ $\gcd(n, x_n)=1$, given $x_{n+1}=2(x_n)^2-1$ and $x_1=2$

I have a sequence $x_{n+1} = 2(x_n)^2-1$; first values are $2, 7, 97, 18817,\dots$ I noticed that if prime $p$ divides $x_n$, then $x_{n+1} \equiv -1\pmod p$ and for all $k>n+1$, $x_k\equiv 1\pmod ...
0
votes
1answer
50 views

A simple equation with a complicated property

Let, $\Bbb{P}$ denote the set of all odd prime numbers and $\Bbb{N}$ be the set of all natural numbers. Let, $2a,2b$ be two even numbers both greater than $4$. Define, $A=\{(p,q)\in\Bbb{P}\times\Bbb{...
3
votes
1answer
38 views

A elementary problem of proving congruences in a statement about absolute Galois group for $\mathbb{F}_{p}.$

I know little bit basic algebraic number theory but do not major in it. This question might be trivial for the experts. I should be ashamed of my failure in proving it. If it is too easy, please ...
0
votes
0answers
48 views

About $\varphi(n)$ I don't know how to get? [on hold]

$$ \sum_{n\mid m}\sum_{d\mid n}d\varphi\left(\frac{n}{d}\right) =\sum_{n\mid m}\sum_{i\mid \frac{m}{n}}n\varphi(i)\\ =\sum_{n\mid m}n\frac{m}{n}=m\sum_{n\mid m}1 $$ so, how to get this? $$ \sum_{n\...
7
votes
2answers
46 views

Prove that if $a, b, c \in \mathbb{Z^+}$ and $a^2+b^2=c^2$ then ${1\over2}(c-a)(c-b)$ is a perfect square.

Prove that if $a, b, c \in \mathbb{Z^+}$ and $a^2+b^2=c^2$ then ${1\over2}(c-a)(c-b)$ is a perfect square. I have tried to solve this question and did pretty well until I reached the end, so I was ...
-3
votes
2answers
32 views
5
votes
1answer
23 views

Let $a<b<c$, where $a$ is a positive integer and $b$ and $c$ are odd primes. Prove that if $a \mid (3b+2c)$ and $a \mid (2b+3c)$, then $a=1$ or $5$.

The prove I tried is the following. I really wish someone can check if I made some logical mistake, especially the last part I found myself diffident proving $a$ can only be $1$ or $5$. Because $b\...
0
votes
1answer
24 views

Basic modular arithmetic question

If for two integers $a,b$, $a=b \mod x$, what is $x$ in terms of $a$ and $b$?. I think the answer is $a-b$, but I'm not sure how to prove it without modular arithmetic, which I don't really ...
12
votes
2answers
111 views

The general proposition of Fermat

In his letter to Frenicle, dated 18th October, 1640, Fermat states the following (Point 8, translated) : If you subtract $2$ from a square, the remaining value cannot be divided by a prime which ...
1
vote
1answer
33 views

If $m, n>0$ and $\gcd(m, n) =d$, then $\gcd(a^m-1, a^n-1) =a^d-1$.

This question has already answered here in other topics, but all answers that I read have some techniques like congruence and fermat numbers and the book which I am reading shows this question in ...
0
votes
1answer
34 views

Proof that a finite series expansion of $f(X)$ at $\alpha$ exists iff $Q(X)$ is a power of $(X-\alpha)$, in $f(X)=\frac{P(X)}{Q(X)}$

I'm working through Gouvea's P-adic numbers book, and early on they give the problem Write $f(X)=\frac{P(X)}{Q(X)}$ in lowest terms, so that $P(X)$ and $Q(X)$ have no common zeros. Show that the ...
0
votes
3answers
45 views

Elementary number theory proof involving multiplied gcd's

I'm having trouble proving the following if and only if statement: For all integers $a,b,n$, prove that $n|gcd(a,n)gcd(b,n)$ if and only if $n|ab$ For proving $n|gcd(a,n)gcd(b,n)\implies n|ab$, I ...
0
votes
2answers
34 views

Find the least nonnegative residue of: $42^{173} modulo 13$

I can across this question: Find the least nonnegative residue of: $42^{173} modulo 13$ I have done the following: $42^{10} ≡ 1 mod 13$ $42^{173} = 42^{10 (17) +3}$ $ 42^{173} ≡ 42^{3} mod 13$ $...
2
votes
2answers
52 views

What are the Legendre symbols $\left(\frac{10}{31}\right)$ and $\left(\frac{-15}{43}\right)$?

I have the following two Legendre symbols that need calculated: $\left(\frac{10}{31}\right)$ $=$ $-\left(\frac{31}{10}\right)$ $=$ $-\left(\frac{1}{10}\right)$ $=$ $-(-1)$ $=$ $-1$ $\left(\frac{-15}{...