Questions tagged [elementary-number-theory]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
28 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.
1
vote
2answers
866 views

Number Theory Homework: Find 3 consecutive integers…

I have this problem assigned for homework, and I'm a bit confused as to how to solve it: Obtain three consecutive integers, the first of which is divisible by a square, the second by a cube, and the ...
4
votes
0answers
84 views

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 ...
4
votes
0answers
43 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 ...
1
vote
2answers
167 views

Product of invertibles in $\Bbb Z_n$ [Wilson's Theorem generalization]

How can we compute the product of all invertibles in $\Bbb Z_n$? In the special case $n=p$ where $p$ is a prime it is Wilson's theorem. By pairing inverses it reduces to computing the product of all $...
2
votes
0answers
19 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
45 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 ...
11
votes
1answer
169 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 17028457$ and couldn't find a prime $...
2
votes
4answers
128 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
211 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 \...
-1
votes
3answers
71 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 ...
3
votes
1answer
53 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,...
5
votes
1answer
246 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 ...
8
votes
2answers
168 views

A prime number wall pool table

Assume we have an idealized even- and $n$-sided pool table with no holes, friction and perfectly reflecting walls, and that a ball is set in motion (inside the table) parallel to one of the sides and ...
3
votes
0answers
396 views

A Special Observation on Prime Numbers and $\pi (n)$

$\eth(n)$ is a little algorithm I made, which may appear to be quite complex, so I will start with an example middle of the post. Questions are at the end of the post. Definition Let $...
2
votes
2answers
54 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 ...
2
votes
1answer
174 views

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

How to prove the following claim ? Let $b_n=b_{n-1}+\operatorname{lcm}(\lfloor \sqrt{n^3} \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 $a_i$ ...
2
votes
0answers
129 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 ...
-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.
0
votes
0answers
39 views

How many multiples of a number are in a (non-consecutive) range of given length?

(Upfront note: This question is different than many similar sounding ones). We are looking at integers. Given is an interval $[L, R]$ of length $[L–R +1]$ and an arbitrary starting point $L$. However, ...
1
vote
0answers
36 views

Is there a specific equation relating $\varphi(N)$ to $\sigma(N)$ when $N = q^k n^2$ is an odd perfect number?

I get $$\gcd(n^2,\sigma(n^2)) = \frac{n^2}{\sigma(q^k)/2} = \frac{\sigma(n^2)}{q^k} = \frac{2n^2 - \sigma(n^2)}{\sigma(q^{k-1})}$$ when $N = q^k n^2$ is an odd perfect number with special/Euler prime $...
0
votes
2answers
43 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
3
votes
8answers
5k views

Prove that $9\mid (4^n+15n-1)$ for all $n\in\mathbb N$

First of all I would like to thank you for all the help you've given me so far. Once again, I'm having some issues with a typical exam problem about divisibility. The problem says that: Prove that ...
1
vote
1answer
39 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 ...
2
votes
1answer
54 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
3answers
79 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 ...
2
votes
1answer
184 views

implication of a number dividing a product of relatively prime numbers

I read this recently on the web and can't manage to understand it. Not homework -- I haven't done math homework for years. If $d|ab$ and $(a,b)=1$, prove that $d=d_1 d_2$, that $d_1|a$, that $d_2|b$, ...
0
votes
1answer
85 views

find all primes $p$ and $q$ such that $p^2+1 | 2003^q+1$ and $q^2+1 |2003^p+1$

If $$p=2$$ then $$p^2+1=5$$ we have $$2003^q+1\equiv 0 [5]$$ $$2003^{2q}-1\equiv 0 [5]$$ let $o_{5}(2003)$ be the order of $2003$ modulo $5$ we have $$o_{5}(2003) |2q$$ $$2003\equiv 3[5]$$ and $$3^4\...
2
votes
3answers
55 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
41 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, ...
3
votes
1answer
51 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 $\...
1
vote
4answers
54 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 ...
0
votes
1answer
40 views

Is there a specific terminology for numbers which are nontrivial multiples of triangular numbers?

(Note: Please see this new question for the motivation.) A number $T$ is said to be triangular if it could be written in the form $$T=\frac{n(n+1)}{2},$$ where $n$ is a positive integer. Here is my ...
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
51 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 ...
2
votes
2answers
151 views

Prove common divisors of $a,b$ divide $\gcd(a,b)$ without Bezout, primes or guessing the form of the GCD

Every proof of this fact that I've seen relies on guessing a "formula" for the GCD first, such as "the smallest positive integer of the form $ax+by$" or $\frac{ab}{\text{lcm}(a,b)}$. Then one shows ...
2
votes
2answers
158 views

is there a faster method to calculate $1/x$ ($x$ an integer) than this?

I gave this stackexchange a second go. Is there a faster way to calculate $1/x$ than the following: Calculate $100/x$ (.or other arbitrary positive power of $10$) with remainder Write multiplier in ...
1
vote
0answers
36 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'$ ...
0
votes
3answers
69 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 ...
1
vote
0answers
54 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 ...
4
votes
3answers
270 views

Quadratic field, $O_K/\mathfrak{p} = \mathbb{F}_p$, $O_K/pO_K$ is a finite field of order $p^2$.

Let $K$ be a quadratic field $\mathbb{Q}(\sqrt{m})$ where $m$ is a square free integer, and let $p$ be a prime number which does not divide $2m$. Where can I find a reference to a proof of the ...
5
votes
2answers
138 views

What is known about the minimal number $f(n)$ of geometric progressions needed to cover $\{1,2,\ldots,n\}$, as a function of $n$?

So a geometric progression can contain at most two primes. This automatically gives a lower bound on the minimal number $f(n)$ of geometric progressions needed to cover the integers $\{1,2,\ldots,n\}$,...
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 ...
1
vote
1answer
54 views

Are there nontrivial perfect powers of integers that are nontrivial repdigits?

For example, $6^5=7776$ is close, but not quite a repdigit. Heuristically, it seems to me that there should not be any, because the longer a number with (effectively) random digits is, the less the ...
20
votes
6answers
51k views

What is meant by “evenly divisible”?

"What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?" Is it different from divisible?
2
votes
2answers
46 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 ...
0
votes
2answers
184 views

Is there a way of finding out the remaining two numbers of pythagorean triple if one of the side is given

I am solving one question related to right triangle and I have to find out the remaining two numbers of the pythagorean triple if one of the number is given. I know there can be many triples possible ,...
1
vote
2answers
51 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 ...
7
votes
1answer
386 views

Prime Number Sieve using LCM Function

How to prove the following conjectures ? Definition : Let $b_n=b_{n-2}+\operatorname{lcm}(n-1 , b_{n-2})$ with $b_1=2$ , $b_2=2$ and $n>2$ . Let $a_n=b_{n+2}/b_n-1$ Conjectures : Every term ...
18
votes
5answers
5k views

How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...