Questions tagged [elementary-number-theory]
Questions on divisibility, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, quadratic number fields and other related topics which may be treated in first courses on number theory. More advanced topics should instead use the number-theory or other tags.
35,757
questions
4
votes
1
answer
36
views
Amount of compositions until $f(x)=x-\lfloor\frac{x}{n}\rfloor$ becomes constant
Suppose I have positive integers $a$ and $n$. I want to find the number of times $f(x)=x-\lfloor\frac{x}{n}\rfloor$ could be composed on itself with initial argument $a$ until a number less than $n$ ...
- 69
-2
votes
0
answers
31
views
Why is $2^{-1}$ (mod 13) equal to 7 while $2^{12}$ (mod 13) equal to 1 [duplicate]
I thought that $\!\bmod p\!:\, {-}1\equiv p-1$? Isn't $\,{-}1\equiv 12 \pmod{\!13}$ and why would exponentiation change that?
- 1
-1
votes
1
answer
50
views
Why is the remainder when $8^{43}$ divided by seven not obtainable by the cycle of four in the units digit when eight is powered? [duplicate]
What is the remainder when $8^{43}$ divided by seven?
$8^{43}=2^{120+9}$
the units digit of $2^x$ cycles in lengths of four from $2,4,8,6$
$4 \cdot 32=128$ 32 cycles of four ended, and we return to ...
- 103
1
vote
0
answers
40
views
Similarity of Lifting the Exponent Lemma in Pell numbers
Pell number is a term of the sequence $\{P_n\}$ determined by a recurrence relation
$$P_{n+2}=2P_{n+1}+P_n, P_0=0, P_1=1.$$
Let $v_p(x)$ be the $p$-adic valuation of an integer $x$ (the number of ...
- 145
1
vote
0
answers
14
views
Reinforcement of the Gauss Lemma (the one about quadratic reciprocity law) [closed]
Let $a$ be a positive odd number.
$b \in \mathbb{Z}$, s.t. $gcd(a,b)=1$
Assuming $\left\{ r_i \right\}_{i=0}^{a-1}$ s.t.$ r_i \equiv bi (\mod a)$,$-\frac{a}{2}<r_i<\frac{a}{2}$
$n$ is the ...
- 11
-1
votes
0
answers
21
views
Find the maximum difference between consecutive integers with the most and the least divisors of interest
Suppose that $a$ is a set of integers with each element $a[i] \ge 2$, and any 2 integers in this list are co-prime. Any $k$ consecutive integers will contain a certain number of integers that divides ...
0
votes
0
answers
32
views
How to prove that $(4n + 3)$ and $(20n + 23)$ are mutualy prime? [duplicate]
Following the next theorem:
$$\gcd(a; b) = \gcd(a - b; b)$$
I get to the point where from these two numbers $4n + 3$ and $20n + 23$ I get these: $4n + 3$ and $8$.
It seems obvious that these numbers ...
- 101
1
vote
0
answers
20
views
cube of any integer is of form $7k, 7k \pm 1$ [duplicate]
To prove : cube of any integer is of form $7k, 7k \pm 1$
Cube of any integer is of form $9k, 9k+1, 9k+8$ (Proved earlier).
Now question is that any integer of form $9k, 9k+1, 9k+8$ also has form $7k, ...
- 2,165
0
votes
0
answers
39
views
How to prove $1^3+5^3+3^3=153,16^3+50^3+33^3=165033,166^3+500^3+333^3=166500333,\cdots$ with mathematical induction?
$1^3+5^3+3^3=153$
$16^3+50^3+33^3=165033$
$166^3+500^3+333^3=166500333$
$1666^3+5000^3+3333^3=166650003333$
$...$
People in the below link proves the above identities.
The proof without mathematical ...
- 11
-1
votes
0
answers
28
views
Diophantus' Identity
Diophantus' Identity says that $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bd)^2$. If both $a^2+b^2$ and $c^2+d^2$ are odd integers, can I show that $2(ac+bd)^2+2(ad-bd)^2$ is a sum of two odd squares? I tried ...
- 311
4
votes
1
answer
130
views
Twice the product of odd numbers [duplicate]
Let $m$ and $n$ be odd integers such that $m$ is the sum of two squares and $n$ is the sum of two squares. I am supposed to show that $2mn$ is sum of two odd squares.
First, since $m$ and $n$ are both ...
- 311
4
votes
1
answer
47
views
Let $T$ be the following set of ordered triplets,$T=\{(a,b,c):a,b,c\in N\}$. Find the number of elements in $T$ such that $L.C.M(a,b,c)=72$.
Let $T$ be the following set of ordered triplets,$T=\{(a,b,c):a,b,c\in N\}$. Find the number of elements in $T$ such that $L.C.M(a,b,c)=72$.
My Attempt
Let $a=2^{x_1}3^{y_1}$,$b=2^{x_2}3^{y_2}$ and $c=...
- 7,819
1
vote
0
answers
22
views
Given $ax=by, a(m^2+n^2)=b(p^2+q^2), (a,b)=(x,y)=1$, show that $a,b$ must also be sums of two squares. [duplicate]
I'm asking for verification of the following proof:
We start with the following equality, working entirely in $\mathbb{Z}$:
$$a(m^2+n^2)=b(p^2+q^2)$$
With $x=m^2+n^2,y=p^2+q^2; a,b$ coprime and $x,y$ ...
- 2,506
-4
votes
1
answer
36
views
A problem involving prime numbers and them dividing some function of themselves. [closed]
A friend sent me this question. This is I guess a previous year question of some Olympiad. I don't know to approach it.
Any small idea that will get me started on this problem will be very helpfull. I ...
0
votes
0
answers
31
views
Show that there are infinitely many primes of the form $3n-1$ [duplicate]
I have seen similar proofs but not one of the form $3n-1$. It seems to be a little different for each form.
Suppose $\{p_1,p_2,...,p_n\}$ is a finite set of primes of the form $3n-1$. Then $3(p_1p_2......
6
votes
1
answer
86
views
Given $p - 1$ integers not divisible by an odd prime $p$, we can change signs of some (all or none) of them so that their sum is divisible by $p$.
I'm currently trying to solve this problems, but ran out of ideas. In my textbook this problem goes after a series of problems related to variations of this zero-sum problem, but it may or may not be ...
- 741
0
votes
0
answers
45
views
Why does the product of the first $n$ prime numbers divided by 4 always have a remainder of $2$? [duplicate]
Multiplying the first $n$ prime numbers $p_1p_2...p_n$ and dividing the product by $4$ we always get $2$ as a remainder. I was wondering why this is the case? Is it because of the factor $2$ in the ...
0
votes
0
answers
20
views
Why choosing $x$ at random from $Z_N^*$ is equivalent to choosing $x_j$ s.t. $x = x_j \pmod{p_j^{\alpha_j}}$ with $p_j^{\alpha_j}$ a factor of $N$. [duplicate]
On the book "Quantum computation and quantum information" from Nielsen and Chuang on page 634 at the beginning of a theorem's proof it's assumed to be able to choose a number $x$ uniformly ...
-2
votes
3
answers
66
views
Prove $(n+1)^{m+1}-(-n)^{m+1}$ is divisible by $2n+1$ [duplicate]
How to prove $(n+1)^{m+1}-(-n)^{m+1}$ is divisible by $2n+1$, with $n,m$ positive integers?
I have tried by induction (on $n$) and with the binomial theorem, something like this (have also assumed $m$ ...
- 9
0
votes
0
answers
60
views
How difficult this RSA cracking algorithm is.
If the way to crack the RSA algorithm is knowing the factors of a number. How easy can the factors be obtained by taking the reverse 'long product'?.
For instance, if you have the product of three ...
3
votes
2
answers
105
views
Is there an efficient algorithm for generating all numbers with n distinct prime factors in order?
Bit of an x y problem here, so in full disclosure, I am attempting to find the next term of A152617, "Smallest number m such that m has exactly n distinct prime factors and sigma(m) has exactly n ...
- 215
0
votes
1
answer
22
views
On line segment subdivision
Suppose I have a line segment, divided into two parts
with $B$ fixed. Is there a way to divide the whole segments into equally spaced subintervals $\Delta x$, such that $AB$ and $BC$ are both ...
- 41
4
votes
1
answer
119
views
How to make sense of this plot $x-\sum[(\text{oddsteps})\mod 3]$
I am trying to make sense of this graph $y=x-\sum\limits_1^x(i\mod 3)$ where $i$ is the number of odd steps for $x$ to reach $1$ in a Collatz sequence.
(plot of $x$ from $1$ to $10^6$)
The graph is ...
- 338
-1
votes
0
answers
28
views
prove that $x^2-2y^2=1$ has infinite integer solutions. [duplicate]
Prove that $$x^2-2y^2=1$$ has infinite integer solutions.
I know this is a case of n=2 in Pell's equation.
But the thing is we are not allowed to use that as a reference in this problem.
And even when ...
- 649
-5
votes
0
answers
98
views
Why my solution in exams is incorrect?
in my exams for number theory my solution took 0 points?
We had the following exercise for the exams:
prove that $38^{12}-34^{4}$ is dividable with $35$.
My Solutions:
$\gcd(35,38)=\gcd(35,34) =1$ so ...
- 9
0
votes
0
answers
48
views
Why the equivalence classes in the quotient set of $a=b\pmod m$ are named $\{0,1,...,m-1\}$ and there are $m$ and not $m+1$ equivalence classes? [duplicate]
I was reading about modular arithmetic. The congruencies modulo $m$ are equivalence relations. The textbook says that for the relation $a\equiv b\pmod m$ the quotient set of the equivalence classes ...
- 133
3
votes
1
answer
27
views
proof for existence of primitive roots mod prime p using $\sum_{d \mid p-1} \varphi(d)$ and $\sum_{d \mid p-1} \psi(d)$
Im reading Number Theory by Andrej Dujella and I'm having a hard time understanding the proof that there are exactly $\varphi(d)$ numbers of order d mod p (p is prime). Here's the proof
Each of the ...
- 33
-3
votes
0
answers
24
views
Proving the existence of md solutions*
Let ax + by ≡ c (mod m) be a linear congruence in two variables x and y and let d = (a, b, m). Prove that if d ̸|c then the congruence has no solutions in integers. Prove that if d|c, then the ...
- 1
-2
votes
0
answers
25
views
Find all positive integers which leaves remainder $1$ when divided by $3$, $2$ when divided by $4$, and $8$ when divided by $10$ [closed]
I have tried finding the general form but it appears that there is no general form. I could try just brute forcing it but it just is impractical.
PS: please only use the following theorems:
Division ...
0
votes
1
answer
35
views
Euclid numbers are always of the form $4m+3$ [duplicate]
The Euclid numbers are defined as $P_n:=p_1p_2...p_n+1$ where the $p_i$ are the prime numbers. I need show that $P_n$ is always of the form $4m+3$ for $m \in \mathbb{N}_0$.
I have found proofs for ...
0
votes
2
answers
74
views
What is the remainder when the expression $\sum_{i=1}^{10} {{10^{10}}^i} $ is divided by 7? [duplicate]
What is the remained when $\sum_{i=1}^{10} {{10^{10}}^i} $ is divided by 7?
I have tried writing $10 = 3+7$ which makes the expression $\sum_{i=1}^{10} {{(3+7)^{10}}^i}= \sum_{i=1}^{10} {(7p+{{(3)^{10}...
- 71
0
votes
1
answer
36
views
$\mathbb{Z}[(1+\sqrt{-19})/2]$ is PID [duplicate]
I am reading Dummit & Foote's book and on page 282, I can't understand the part that I have offset and bolded in the following quote. How can we conclude that $ay-19bx=cq+r$? I know that there is ...
- 133
1
vote
0
answers
43
views
Name for integer "quotient" rounded up (ceiling) instead of down (floor), and its negative or complementary "remainder"
If $168$ cookies (dividend) are shared between $17$ people (divisor), that's almost $10$ cookies each but we're $2$ cookies "short"; alternatively we have slightly more than $9$ cookies each ...
- 1,327
3
votes
0
answers
126
views
+50
What triplets satisfy this condition using floors?
Below, $r_1,r_2,r_3$ are positive real numbers such that $r_1+r_2+r_3=1$, $m$ is an arbitrary positive integer, and $m_i := \lfloor r_i\cdot m\rfloor$ for all $i\in [3]$.
Define the triplet $(r_1,r_2,...
0
votes
0
answers
41
views
Is there a name for when two numbers have the same sums of divisors?
If $a,b$ are integers and $\sigma$ is the sum of divisors function and $\sigma (a) = \sigma (b)$ is there a name for this?
For instance $\sigma (14) = \sigma (15) = 24$
- 149
2
votes
0
answers
154
views
Is there a hidden relation between the sum of squares and the factorial?
Is there a hidden relation between the sum of squares and the factorial?
Two cases will be considered: the sum of odd squares and that of the even squares. We will not consider the classical sum of ...
- 880
-1
votes
1
answer
40
views
Cardinal of a specific set
I was trying to prove that $${\rm card}\{ (k,n)\in\mathbb{N}^*\times\mathbb{N}; k(2n+1+k)=\text{ product of the first i prime numbers } \}=2^{i-1}.$$
Calculations for $2,2\times 3,2\times 3\times 5$ ...
- 1
0
votes
2
answers
81
views
How many ordered pairs $(x, y)$ of positive integers satisfy $x^2−2y^2=1$, where $y$ is prime?
How many ordered pairs $(x, y)$ of positive integers satisfy the
equation
$$x^2 − 2y^2 = 1$$
where $y$ is a prime number?
(A) $0\;$ (B) $1\;$ (C) $2\;$ (D) $4$
I am getting a ordered pair $(3,2)$ ...
3
votes
1
answer
62
views
What is the probability that the greatest prime factor of a sequence of uniformly distributed integers increases?
Let $f_k(n), n = 1,2,3...$ be a sequence of random integer uniformly distributed in $[2,k]$ for some fixed $k \ge 3$. Let $l_n$ be the largest prime factor of $f_k(n)$. What is the probability that $...
- 16.3k
3
votes
1
answer
49
views
Given $n$ not prime, is there always a $1<k<n$, such that $n \nmid \binom{n}{k}$?
My kid shared something from internet on Pascal's triangle that, if $p$ is a prime, then for the $p$-th row, except the beginning and ending $1$, each number is divisible by $p$. This is, of course, ...
- 4,731
1
vote
2
answers
69
views
Sum of co-primes of a number $n \le k$
Problem
Given a number $n$ and a number $k$ ($k\leq n$) we are to find
sum of co-primes of $n$ less than or equal to $k$
My thoughts
factorise $n$
and then do $k(k + 1)/2$ - ...
- 421
0
votes
1
answer
79
views
Why is $f(x)\equiv f(x+2k)\pmod k$ for$ f(x)=x(x+1)/2 + c.$
I came across this in a programming contest:
f(x)%k = f(x+2k)%k for f(x)=x(x+1)/2 + c
I first thought that this is a property of Harmonic numbers only but after ...
- 453
0
votes
1
answer
46
views
When can two integers of this form be said to belong to the same set?
If I have two numbers $a_1$ and $a_2$ of the form:
$$
a_1=b_1 C+d_1\mod E
$$
and
$$ a_2=b_2 C+d_2\mod E $$
where I know $C$ and $E$ but $b_1$ and $b_2$ are arbitrary positive integers. Under what ...
2
votes
2
answers
68
views
Find a good starting point to search for $n$ consecutive composite numbers.
I'd like to use the Prime Number Theorem (PNT) to find a good starting point to search for $n$ consecutive composite numbers.
The PNT says
For large enough $x$, the probability that a random integer ...
- 1,253
3
votes
2
answers
87
views
How to prove the existence of a Pythagorean Triple without finding solutions?
I am looking to prove that there is a Pythagorean Triple (x, y, 173) without finding solutions.
I know that a solution does exist ((52, 165, 173)), however I would like to prove this more generally (...
- 183
0
votes
1
answer
50
views
Sufficiently large prime numbers $6z + 1$ are not all of the form $36xy - 6x + 6y + 1$ for $x,y \neq 0$?
The polynomial $36xy - 6x + 6y + 1$ seems to be irreducible over $\Bbb{Z}$ or even $\Bbb{Z}[i]$. I don't know if that matters, but, I don't think all large enough primes of the form $6z + 1$ can &...
- 19.8k
0
votes
2
answers
81
views
In how many ways can $2^5\times 3^7$ be factored into three setwise coprime integers?
Let $T$ be the following set of ordered triples, $T=\{(a,b,c):a,b,c\in \mathbb{N}\}$.
Find the number of elements in $T$ such that $abc=2^5\times 3^7$ and $\gcd(a,b,c)=1$
My Attempt
If $a=2^x;b=3^y;c=...
- 7,819
-2
votes
0
answers
127
views
For each prime number p>2, state how many solutions x∈Z/p there are to the equation x^(p^2 )+x=1 mod p [closed]
I'm trying to prove the following:
For each prime number p>2, state how many solutions x∈Z/p there are to the equation:
x^(p^2 )+x=1 mod p
and justify your answer with a proof.
1
vote
0
answers
44
views
maximum with factorials
Let $k>2$. Can we determine $\displaystyle \max_{m\in\mathbb N}\frac1{k10^{m!}}-\frac2{10^{(m+1)!}}$ ?
Or at least a non trivial lower bound of this maximum?
That is in relation with thread
Thanks ...
- 1,063
3
votes
1
answer
83
views
Number of prime solutions to $a^2 + b^2 = c^2 + 241$ such that $a^3 + b^3 + c^3$ is also prime
Are there finitely or infintely many prime solutions to $a^2 + b^2 = c^2 + 241$ such that $a^3 + b^3 + c^3$ is also prime?
Richard Borcherd's first lecture on algebraic geometry has, as an example, a ...
- 9,228