Questions tagged [elementary-number-theory]

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

Filter by
Sorted by
Tagged with
-2
votes
3answers
48 views

How do I prove the following properties about prime numbers?

Let $p$ be a prime number not equal to 2 or 3 Prove that $p\equiv 1\pmod{6}$ or $p\equiv -1\pmod{6}$ Prove that if $p+2$ is also a prime,then $p+1$ is divisible by 6
0
votes
0answers
38 views

How to check if N is prime or not، when you have the factors of (N-1) [on hold]

How to check if (N) prime or not, using $N-1$ factors, pocklington primality test for example can be used to check these numbers, is there any other methods ?
3
votes
0answers
81 views

Diophantine equation: $n^2=c(4ab-a-b)-b$?

Let $n$ be a positive integer. The Diophantine equation $$ n^2=c(4ab-a-b)-b,\qquad (a,b,c\in\mathbb{Z}^+) $$ is solvable for $n\equiv\pm1\pmod3$, but I stuck for $n\equiv0\pmod3$. Is there any ...
2
votes
1answer
84 views

Compute $\gcd(a+b, 2a+3b)$ if $\gcd(a,b) = 1$

A question from a problem set is asking to compute the value of $\gcd(a+b, 2a+3b)$ if $\gcd(a+b) = 1$, or if it isn't possible, prove why. Here's how I ended up doing it: $\gcd(a,b) = 1$ implies ...
4
votes
2answers
219 views

How to find the consecutive odd numbers that sum to a given odd number

Given an non perfect square odd number, say $1649$ What is the most efficient way to find the consecutive odd positive integers that sum to that number. No other information is provided, just the odd ...
3
votes
2answers
86 views

Proof explanation: suppose $a\mid bc$ and $\gcd(a, b) = 1$. Then $a\mid c$.

I have been given a proof, but I do not understand the "why" behind it. If someone could explain me each of its steps with great detail that would be amazing! The proof I was given is the following ...
5
votes
4answers
89 views

Is every prime contained in the set $\,\{n\in\mathbb{N}:n|10^k-1\}\cup\{2,5\}\,$ for $k=1,2,3,…$?

Is every prime contained in the set $\,\{n\in\mathbb{N}:n|10^k-1\}\cup\{2,5\}\,$ for $k=1,2,3,...$? Let $p\notin\{2,5\}$ be a prime number. Then $\frac{1}{p}$ has a decimal period of length at most ...
2
votes
3answers
62 views

Solving $x^5+px^2y^3+p^2y^5 = 0$ where $p$ is prime and $x,y \in \mathbb{Z}$

How do you solve $x^5+px^2y^3+p^2y^5 = 0$ where $p$ is prime and $x,y \in \mathbb{Z}$? Working in modulo $p$ we have $x^5 = 0 \pmod{p}$ and $x = 0$ which is the only solution in modulo $p$ since $a^...
6
votes
2answers
85 views

Let $p,q > 2$ be distinct primes. Show that $\mathbb{Z}_{pq}^*$ is not cyclic.

I recognize this question has been asked many times before (here, here, and here) and in other forms (that $pq$ does not have a primitive root for example). I am also self-studying Aluffi's Algebra ...
1
vote
2answers
73 views

How many primes are there of the form $x^6+y^6$, where $x,y\in\mathbb{Z}$?

I'm trying to find such primes that are of the form $x^6+y^6$; $x,y\in\mathbb{Z}$. If one of $x$ and $y$ is $0$, say $y=0$ then $x^6+y^6=x^6$ which is not a prime. So assume that $(x,y)\ne(0,0).$ I ...
2
votes
2answers
57 views

How to find Residue of Power Integer

I found congruence like below in various note- $$ 6^x \equiv 16 \pmod{20}$$ $$ 5^z\equiv 5 \pmod{20}$$ For any $z,x$ (perhaps, I didn't see any other condition). How residues $16, 5$ are found? ...
1
vote
2answers
37 views

When to apply well ordering principle?

Proof of the Division Algorithm In many books on number theory they define the well ordering principle (WOP) as: Every non-empty subset of positive integers has a least element. Then they use this in ...
4
votes
2answers
121 views

On Composite Numbers of the Form $p_{1}p_{2} \ldots p_{k} - 1$

This question is related to D. H. Lehmer's 1932 conjecture on Euler's totient function: Are there any composite $n$ for which $\phi(n)$ divides $n-1$? See, for example: On Lehmer's Totient ...
0
votes
1answer
86 views

number of primes less than a number $N$ is $\tfrac{N}{\log(N)}$ ??

In my lecture notes it says that for $N \in \Bbb N$ there are $\tfrac{N}{\log(N)}$ primes which are less than $N$. But say $N=20$, the primes less than $20$ are $1,2,3,5,7,11,13,17,19$, so there are ...
4
votes
3answers
141 views

It is impossible for $(x-1)^2+x^2+(x+1)^2$ to be a perfect square

Prove that it is impossible for three consecutive squares to sum to another perfect square. I have tried for the three numbers $x-1$, $x$, and $x+1$.
0
votes
2answers
60 views

How to solve $y^3=x(x+1)$ where $x$ and $y$ are integers? [on hold]

How to solve $y^3=x(x+1)$ where $x$ and $y$ are integers ? Can you help me ? Thanks :)
0
votes
0answers
40 views

Prove that $(a+b)/(c+d)$ is a fraction in lowest terms if $ad − bc = 1$. [duplicate]

I have deduced that the $gcd(a,b)=1$ and the $gcd(c,d)=1$. I also figure since $(a+b)/(c+d)$ is a fraction in lowest terms $gcd(a+b,c+d)=1$ but from there I really have no idea what to do.
5
votes
0answers
103 views

Does there exist some prime $k$ for which there will be exactly two primes of the form $n!+k$?

This is a question related to my recent question Conjecture: “For every prime $k$ there will be at least one prime of the form $n!\pm k$” true? Using PARI/GP I searched for the number of primes of ...
4
votes
0answers
150 views
+50

Has $n^{n+1}+(n+1)^{n+2}$ other obvious factors than that I found?

Has the number $$f(n):=n^{n+1}+(n+1)^{n+2}$$ "obvious" factors (algebraic, aurifeuillan or similar kinds) apart from those , I mention below ? I only managed to find out forced factors for odd ...
5
votes
1answer
45 views

What is the ratio of Carmichael pseduo-primes to true primes for $1$ to $n$? Or is it known?

Let $\pi(n)$ be the prime counting function. And let $\varphi(n)$ be the count of Carmichael pseudo-primes for $1$ to $n$. Is the ratio, $$\frac{\varphi(n)}{\pi(n)}$$ is known, as $n \to \infty$? I ...
3
votes
2answers
67 views

Rational points on $2x^2+2y^2=1$ and integral solutions to $2X^2+2Y^2=Z^2$

(a) Find a solution to the diophantine equation $2X^2+2Y^2=Z^2$; hence find a solution for rational numbers of the form $2x^2+2y^2=1$. We have $2X^2+2Y^2 \equiv Z^2\pmod{2} \implies (X,Y,Z) =c(1,1,...
2
votes
4answers
134 views

If $a \equiv b \pmod n$ and $c+d = n$, does $ca+bd \equiv 0 \pmod n$?

I am trying to prove a different equation and am able to if the following is true, but I am not exactly sure if it is true. If $a\equiv b \pmod{9}$ and $c+d = 9$, is $ca+bd \equiv 0 \pmod{9}$ a true ...
8
votes
1answer
224 views

Relationship between GCD, LCM and the Riemann Zeta function

Let $\zeta(s)$ be the Riemann zeta function. I observed that as for large $n$, as $s$ increased, $$ \frac{1}{n}\sum_{k = 1}^n\sum_{i = 1}^{k} \bigg(\frac{\gcd(k,i)}{\text{lcm}(k,i)}\bigg)^s \approx \...
11
votes
2answers
244 views

Conjecture: “For every prime $k$ there will be at least one prime of the form $n! \pm k$” true?

Using PARI/GP, I searched for primes of the form $n!\pm k$ where $k \ne 2$ is prime and $n\in \Bbb{N}$. With the help of user Peter, we covered a range of $k \le 10^7$ and couldn't find a prime $k$ ...
1
vote
2answers
45 views

Prove that if $a>b$, then $a>2r$; let $r$ be the remainder of $a$ divided by $b$

Overall this is intuitive and yet hard to proove. I was thinking about demonstrating this starting from $a<2r$ until I get to a contradiction but I can't find one a small help is appreciated
-1
votes
1answer
43 views

Prove that 3 divides $a \times b \times ( a^2 − b^2 )$. [on hold]

This is so random and I can't get to the key. All I'm thinking about is to proof that $a \times b \times ( a^2 - b^2 )$ is three numbers that are followed by each other but I can't prove it.
1
vote
1answer
40 views

Why does $a^p = mb + 1$? (An Encryption Problem)

I was watching the minutephysics video on why quantum computers break encryption, and they brought up that $a^p = mb + 1$, or rather that for any two numbers that may not share factors, one of the ...
-1
votes
2answers
76 views

$x^2 ≡ -a^2 (\mod p)$ if and only if $ p ≡ 1 (\mod 4)$ [on hold]

I need help proving the following: Let p be an odd prime and a be any integer which is not congruent to 0 modulo p. Prove that the congruence $x^2 ≡ -a^2 (\mod p)$ has solutions if and only if $p ≡ 1 ...
1
vote
0answers
44 views

Is the largest order of an element of a group always the size of the group? [duplicate]

Similar to how one can find a primitive root element of $\mathbb{Z}/p\mathbb{Z}$, I was wondering if, for any group of size $N$ that can be written as $(k\backslash\{0\},\cdot)$ where $k$ is a field, ...
1
vote
3answers
80 views

Solving the diophantine equation $x^3+y^3 = z^6+3$

I've the following problem: Show that the congruence $x^3+y^3 \equiv z^6+3\pmod{7}$ has no solutions. Hence find all integer solutions if any to $x^3+y^3-z^6-3 = 0.$ We can rearrange the first ...
1
vote
1answer
21 views

Does the maximum number of roots in a field directly imply the maximum number of solutions in a group

From Proposition 2.5 from https://wstein.org/edu/2007/spring/ent/ent-html/node28.html#prop:dsols, the maximum number of roots $\alpha\in k$ of $x^n-1$ in a field $k$ is $n$. That is, there are at most ...
-1
votes
0answers
53 views

find the number [on hold]

I have $N$ prime numbers $p_1, p_2 , p_3, \dots ,p_N$. Now there is one of these primes $P$ which is divided by a number $x^2$ to get a remainder which I can know. How should I select $x$ in order ...
1
vote
4answers
55 views

Finding all elements in $x\in U_{143}$ such that $x^2=1 \pmod{143}$ [duplicate]

Find all elements in $x\in U_{143}$ such that $x^2=1 \pmod{143}$ I am kind of stuck here. I know that $143=11*13$, and perhaps looking at $U_{11},U_{13}$ will help but I am unable to find a solution ...
3
votes
2answers
55 views

Numbers which can be expressed as arithmetical combinations of the numbers $1$ through $N$

Let's say a number $M$ is an arithmetical combination of $\{1, 2 \cdots, N\}$ if it can be expressed satisfying the following constraints: the only symbols one can use are $+, \times$, parentheses and ...
1
vote
0answers
37 views

How to prove that the divisors of $a$ and $b$ in common divide the $\gcd(a,b)$ [duplicate]

Let $c$ divide both $a$ and $b$, and let $d=\gcd(a;b)$. How can we prove that $c\mid d$? Here's what I have tried: Let $d$ be $d=\gcd(a;b)$ and $a=d\times a'$ and $b=d\times b'$, where $a'$, $b'$ ...
2
votes
3answers
61 views

Cyclic Remainders [duplicate]

When I was doing my math team training, I encountered a hard question again. Let $x,y,z$ be positive integers that $x<y<z$ with $$\begin{cases} yz\equiv1\mod x\\ zx\equiv1 \mod y\\xy\equiv1\...
1
vote
0answers
64 views

How many odd twin composite pairs are there?

I was wondering, if there is a formula to determine how many odd composite pairs there are until a given $n\in\mathbb{Z}^+$ like $(25,27), (33,35), etc.$ Theoretically it can be calculated, because ...
0
votes
4answers
72 views

Solving $84m+165n=117$ over $\mathbb{Z}$

I have two integers $m,n\in \mathbb{Z}$ and I would like to find in order to solve the following equation over $\mathbb{Z}$: $$84m+165n=117$$ I guess we need to use the Euler algorithm but I'm not ...
2
votes
1answer
57 views

Factors of binomial coefficients [on hold]

I am looking for some ideas to prove or disprove the following conjecture: Let $p$ be a an odd positive integer. Then $2^n$ divides $\binom{2^np}{k} $ for any integer $0<k<2^np$. Thanks for ...
1
vote
1answer
22 views

Can at least one primitive root $w$ of $N$ be expressed as $a^2-b$, where $(b|N)=-1$

I am stuck on a thought experiment: can any (or for that matter, at least one) primitive root $w$ of $N$, $N$ prime, be expressed as $w=a^2-b$, where $(b|N)=-1$, and $a,b\in\mathbb{N}$. We know that ...
3
votes
1answer
53 views

Existence of a finite field element whose image under a quadratic map is a generator

Let $\mathbb{F}_q$ be a finite field of characteristic $p=2$. Let $c\in \mathbb{F}_q$. Does there always exist $a\in\mathbb{F}_q$ such that $b:=a^2+ca$ is not contained in any proper subfield of $\...
2
votes
2answers
56 views

Method for finding the coefficients in Bezout's identity without using extended euclidean algorithm [on hold]

Every book I have seen uses the extended euclidean algorithm for computing the coefficients of Bezout's identity. I feel that it is very tedious and time consuming. Is there a simpler and shorter ...
1
vote
2answers
52 views

Finding modular inverse by solving diophantine equation

Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this ...
5
votes
1answer
305 views
+100

Generating prime numbers of the form $\lfloor \sqrt{3} \cdot n \rfloor $

How to prove the following claims ? Let $b_n=b_{n-1}+\operatorname{lcm}(\lfloor \sqrt{3} \cdot n \rfloor , b_{n-1})$ with $b_1=3$ and $n>1$ . Let $a_n=b_{n+1}/b_n-1$ . Every term of this sequence ...
2
votes
1answer
50 views

Structure of integer pairs which commute under exponentiation

In the natural numbers, exponentiation is defined as a non-commutative operation, but there are some pairs $\{a,b\}$ for which $a^b=b^a$, like for example, $\{2,4\}$. Is there any mathematical ...
-3
votes
0answers
40 views

Question on the Smallest Subgroups of $~\mathbb Z$ Containing $8$ and $14$ [closed]

Find the smallest subgroups of $~\mathbb Z~$ containing $~8~$ and $~14~$.
9
votes
0answers
91 views

Conjecture: Is the identity $2^5-5^2=2+5$ unique? [duplicate]

Yet again a conjecture! Motivated by Catalan's conjecture and a recent question of mine, I conjecture that For distinct, positive integers $a,b$, the only solution to this equation $$a^b-b^a=a+b\...
1
vote
1answer
70 views

How old is Legendre's conjecture?

When did Legendre stipulate his conjecture that there is a prime between $n^2$ and $(n+1)^2?$
2
votes
0answers
139 views

Generating prime numbers of the form $\lfloor \sqrt{2} \cdot n \rfloor $

How to prove the following claims ? Let $b_n=b_{n-1}+\operatorname{lcm}(\lfloor \sqrt{2} \cdot n \rfloor , b_{n-1})$ with $b_1=2$ and $n>1$ . Let $a_n=b_{n+1}/b_n-1$ . Every term of this sequence ...
2
votes
2answers
55 views

If $n$ is the sum of two squares, then $n$ is not congruent to $3\pmod 4$

I have to prove that if $n\in\mathbb{Z}$ is the sum of two squares, then $n\not\equiv3\pmod4 $. I tried to do a proof by contradiction (showing that a contradiction arises using the form $p\wedge\neg ...