Questions tagged [elementary-number-theory]

For questions on introductory topics in number theory, such as divisibility, prime numbers, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, quadratic number fields, Pell's equations, and related topics.

Filter by
Sorted by
Tagged with
5 votes
0 answers
126 views

$x^5=y^2+10$ has no solutions

I am looking for an elementary way to show the equation $x^5=y^2+10$ has no integer solutions. I have checked the equation mod $n$ for $n<1000$ and it had solutions every time. Here is my proof, ...
ForgeBloyb's user avatar
0 votes
2 answers
47 views

Manual Primality Testing methods

I am curious to know some other interesting manual methods for Primality testing. Here is one of the methods I know as of now. Suppose let us say, we need to check whether $397$ is Prime or not. We ...
Ekaveera Gouribhatla's user avatar
0 votes
0 answers
49 views

Using FTA to prove exponential relation between integers [duplicate]

Question: Show that if $x$ and $y$ are non-zero integers and $x^2 = y^3$ then $x=a^3$ and $y=b^2$ for some integers $a$ and $b$ My attempt: If $y^3 = x^2$ then this means $y$ is a natural number, ...
altayir1's user avatar
0 votes
1 answer
76 views

Are there sets that are so unique that even multisets can't share a sum with them?

For sets that don't have $1$s or $0$s and all numbers are whole numbers. We already know $A$ = {$a,b,c...$} and it has distinct subset sums. For multisets consisting of only elements from $A$, can we ...
The T's user avatar
  • 191
2 votes
1 answer
61 views

Solve $10^k\equiv 2^k\pmod{2^{k+1}}$ & $10^j+10^k\equiv 2^j+2^k\pmod{2^{k+1}}.\,$ Binary digits ends with its decimal digits (with at most two 1's)

Find all positive integers $n$ such that the binary representation of $n$ ends with its decimal digits and contains at most two 1's in its decimal representation. Here is my current approach: $$ n_{...
SpungLung's user avatar
1 vote
0 answers
35 views

Efficient proof that a number is NOT a Zumkeller number?

The subset sum problem is known to be NP-complete , so in general there is no efficient method to decide it , in particular to prove a negative result. This problem arises in the problem to decide ...
Peter's user avatar
  • 84.5k
0 votes
2 answers
41 views

Animal Inheritance Puzzle

The animal inheritance puzzle can be formulated as finding naturals $a,b,c$ such that $$\frac1a + \frac1b + \frac1c + \frac1{\operatorname{lcm}(a,b,c)} = 1$$ The numerator of the rightmost addend is ...
Ali Kwant's user avatar
2 votes
0 answers
39 views

Miller Rabin Primality Test - Least Witness Proof, Legendre Symbol

I am currently reading Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance, and I cant seem to see how part of a proof is derived. Here is some background: Strong ...
James S's user avatar
  • 21
2 votes
1 answer
178 views

Separating Gamma function in two independent functions: $ \Gamma(n-m) = f(n)g(m) ?$

I've encountered a problem in my PhD. I would greatly appreciate any suggestions, tips, or comments you might have. The problem is Let $\Gamma(z)$ be the gamma function. Given integers $n > m$, ...
curiosity96's user avatar
-2 votes
1 answer
92 views

Prove $7$ divides $13^n- 7^n-6^n$ for any positive integer [duplicate]

I need to prove $7 \mid (13^n - 7^n - 6^n)$ for any positive integer $n$. Using induction I have the following: Base case: $n=2$: $13^2 - 7^2 - 6^2 = 169 - 49 - 36 = 84 \implies 7 \mid 84$ So, ...
kbaggggg100500's user avatar
0 votes
2 answers
66 views

Sum of reciprocals of norms of Gaussian primes

A Gaussian integer is of the form $m+ni$ for $m,n\in\mathbb{Z}$. $m+ni$ is a subset of the Gaussian primes (denoted $\mathbf{P}$) if $m^2+n^2$ is a square of a prime congruent to $3\pmod{4}$ in $\...
alidixon222's user avatar
-3 votes
2 answers
62 views

Finding numbers $n \in \mathbb{N}$ which satisfies the two conditions [closed]

Finding numbers $n \in \mathbb{N}$ which satisfies the two conditions $\phi(n)$ is a perfect square, where $\phi$ is the Euler totient function function $n < 100$ and is not prime I've attempted ...
IcedTea's user avatar
  • 43
1 vote
2 answers
38 views

$n, k, m$ is positive integer and $n, k$ satisfies $n=7k-1$. Prove that for every $d$ which is positive divisor of n, $d+\frac{n}{d}\ne3^{3m-2}$.

$n, k, m$ is positive integer and $n, k$ satisfies $n=7k-1$. Prove that for every $d$ which is divisor of n, $d+\frac{n}{d}\ne3^{3m-2}$. What I've tried: I've shown that there's no such $n$ that works ...
user526256's user avatar
2 votes
2 answers
93 views

Proof that the $(n+1)$-th prime is less than or equal to the $n$-th primorial.

Assuming that $p_{n}$ is the $n^{ th}$ prime and $p_{n}\text{#}$ is the $n^{ th}$ primorial, what is a proof in elementary number theory that, for all $n \ge 2$, $p_{n+1} \le p_{n}\text{#}$ ?
user3134725's user avatar
1 vote
0 answers
96 views

How to solve this problem when $m$ is an odd number?

$m\in \mathbb{N}^*$ is given. There is an array consists of prime numbers, $p_1,p_2,···$ s.t. $p_n$ is the largest prime factor of $p_{n-1}+p_{n-2}+m$, when $n\geq3$. Prove that the array is bounded. ...
Yan Chi-Yueh's user avatar
1 vote
2 answers
39 views

Puzzle: variant of Identify the counterfeit bag

You have 10 bags of 100 coins, and in all of them except for one, every coin weighs exactly 10 grams. However, in the counterfeit bag, all coins weigh either 9 or 11 grams. You need to identify the ...
Cidatama 0's user avatar
0 votes
1 answer
31 views

If $p$ is prime number what are his predecessor and successor $p-1$ and $p+1$ [duplicate]

I suppose that $p-1$ is even number and that $p+1$ is divisible by 3 or vica versa. My first problem is that I needed to prove that $p^2 -q^2$ is always divisible by 24 for $p,q$ being prime numbers ...
Stephanie V's user avatar
0 votes
1 answer
31 views

Multiplication of Real Characters

At the beginning of Sec 9.3. of Montgomery/Vaughan's Multiplicative NT the following comes without explanation: Suppose that χ is a character modulo q, that $q = q_1q_2 $, $ (q_1, > q_2) = 1$, $...
Ali's user avatar
  • 183
0 votes
2 answers
61 views

Exercise 1 Section 9.2. Montgomery/Vaughan's Multiplicative NT

I am trying to show that for any integer $a$, $$e(a/q) = \sum_{d|q, d|a} \dfrac{1}{ϕ(q/d)} \sum_{χ \ (mod \ q/d)} χ(a/d) τ(χ).$$ First I considered the case $(a,q)=1$ and the mentioned equality holds. ...
Ali's user avatar
  • 183
-1 votes
1 answer
37 views

Re-arranging mobius function using recursion [closed]

Consider the Mobius function given by $\Sigma_{d|n}\mu(d)=I(n)\begin{cases}1 & \text{if n=1} \\ 0 & \text{if n>1}\end{cases}$. My book claims that using recursion this formula can somehow ...
summersfreezing's user avatar
0 votes
1 answer
27 views

Lemma 9.11 Montgomery/Vaughan's Multiplicative NT

In the last step of the proof of Lemma 9.11 in the book Multiplicative number theory I: Classical theory by Hugh L. Montgomery, Robert C. Vaughan I couldn't understand the two equalities of the ...
Ali's user avatar
  • 183
0 votes
0 answers
38 views

Show that $ \gcd(3\cdot2^n + 1, 2^{2n}- 3)$ is either $1$ or $13$. [duplicate]

Suppose that $d_n = \gcd(3\cdot2^n + 1, 2^{2n}- 3)$, where $n>0$. Show that $d_n$ is either $1$ or $13$. I tried to use the fact that $\gcd(a,b)=\gcd(a,a-b)$, but I couldn't go much further than ...
Diego Cândido's user avatar
-1 votes
0 answers
44 views

Repeated sum of digits of a nonzero multiple of 3 is 3, 6 or 9. - Related concepts? [duplicate]

Take any (positive) multiple of 3. Say 57. Add digits 5+7=12. Add digits again 1+2=3. I believe repeated sum of digits of any multiple of 3 is going to end up 3, 6 or 9 unless the original multiple is ...
BCLC's user avatar
  • 13.5k
4 votes
3 answers
149 views

Determine the pairs $(x,y)$ of integers satisfying $2x^2-3xy+y+1=0$.

the question Determine the pairs $(x,y)$ of integers with the propriety that $$2x^2-3xy+y+1=0$$ my idea I tried writing it as a product of terms but got to nothing useful. Then I applied the quadric ...
IONELA BUCIU's user avatar
  • 1,271
-3 votes
0 answers
55 views

Is there any mathematic and algebric formula for the 2 -adic valuation of natural numbers? [closed]

I've recently discovered a formula for primes called prime factory of willan's So , i've wondered if there's also a mathematical formula for the 2 -adic valuation of natural numbers ? Her's some ...
Mohamed Lhachimi's user avatar
1 vote
2 answers
121 views
+50

Squares of sum of digits of numbers part 3

This is the third part of my first post about properties of sum of squares of a number. Anyone who is new may refer to the link below. Squares of sum of digits of a number Here is a quick summary: ...
Aarush Saharan's user avatar
3 votes
0 answers
68 views

The number $1^1 + 3^3 + 5^5 + .. + (2^n - 1)^{2^n-1}$ is a multiple of $2^n$ but not a multiple of $2^{n+1}$

Prove that for all $n>1$ the number $1^1 + 3^3 + 5^5 + .. + (2^n - 1)^{2^n-1}$ is a multiple of $2^n$ but not a multiple of $2^{n+1}$. Proof: Let $$S_n=1^1 + 3^3 + 5^5 + .. + (2^n - 1)^{2^n-1}$$ We ...
Penguin's user avatar
  • 101
0 votes
0 answers
15 views

how do we construct a number from multiple congruence conditions? [closed]

If we have multiple congruence conditions n = a mod p_1, n = b mod p_2, n = c mod p_3, how do we construct a specific n which meets all conditions? Also, is the answer unique?
Jacoberu's user avatar
1 vote
1 answer
81 views

For how many values of $m$, is $m, m+4, m+14$ a prime? [duplicate]

I came across this question by accident. The question is, For how many integer values of $m$; will $m, m+4, m+14$ all be prime numbers. Using grunt work, I found that between $1-100$, only $m=3$ ...
CosmicFlaw's user avatar
3 votes
0 answers
27 views

Does a set with no divisibility pairs necessarily have arbitrarily large gaps? [duplicate]

The set of prime numbers has the following properties: No element is divisible by any other element. We can find arbitrarily large gaps between consecutive elements. Does (1) imply (2) for arbitrary ...
Karl's user avatar
  • 11.5k
-1 votes
0 answers
34 views

Fermat's Little Theorem, but the exponent is one-half of one plus the modulus? [duplicate]

I came across the problem $$37^{12} \equiv x \mod 23$$ And I don't know how to solve it. However, I noticed that the exponent was one-half of one plus the prime modulus, which as well occurred in ...
Alexandra's user avatar
  • 451
3 votes
1 answer
103 views

When is $a^x + b^x \equiv a + b \pmod{n}$? [duplicate]

I came across the following result earlier: $$(4^7 + 2^7) = 0 \pmod 6$$ Which I've seen occur in other forms before, leading me to speculate that there exist numbers n and x such that $$a^x + b^x \...
Alexandra's user avatar
  • 451
-2 votes
0 answers
80 views

How to determine if the following expression is necessarily an integer [duplicate]

How can I prove that: $$\frac{30!}{(10!)^3} \in \mathbb Z$$ The question spontaneously occurred to me, but I'm unsure about the best approach to answering it. I apologize for the brevity of my ...
someone's user avatar
  • 21
-2 votes
1 answer
62 views

If $\varphi(n)=2p$ then $p$ is a Sophie Germain Prime [closed]

Define $n,p\in\mathbb{N}$ with p prime. I'm struggling to show that if $\varphi(n)=2p$, then $2p+1$ is prime.
Donald fischer's user avatar
-1 votes
0 answers
34 views

How can I prove this statement about a Diophantine relation?

I am after a proof of the following Diophantine relation. Below I have the proof constructed so far. This is not for an assignment, just recreational math and adult learning. I would like to know if I'...
CommaToast's user avatar
5 votes
0 answers
59 views

Primes of the form $F(a^{k+1})/F(a^k)$

Letting $F(n)$ be the $n$'th Fibonacci number, for what $a$ and $k\ge 1$ is $F(a^{k+1})/F(a^k)$ prime? I know of just $6$ examples: $$\eqalign{ 3 &= F(2^2)/F(2^1)\cr 7 &= F(2^3)/F(2^2)\cr 17 &...
Robert Israel's user avatar
4 votes
0 answers
50 views

Can we efficiently check whether a number is a Zumkeller number?

A positive integer $n$ is a Zumkeller number iff its divisors can be partitioned into two sets with equal sum. If $\sigma(n)$ denotes the divisor-sum-function , this means that there are distinct ...
Peter's user avatar
  • 84.5k
3 votes
3 answers
106 views

Finding $2$ positive integers $a$ and $b$ that $(a!+b)(b!+a)$ is exponentiation of 5

How to find all 2 positive integers a, b such that $(a!+b)(b!+a)$ is expotation of $5$ What I tried: Without loss of generality assume $b ≤ a$ so let $(a!+b) = 5^m$ and $(b!+a) = 5^n$ ($n≤m$ and $m,n ...
nth's user avatar
  • 91
0 votes
0 answers
69 views

Looking to improve an algorithm for decomposing an integer

I'm interested with primorial number system. In this playful setting, out of curiosity and for relaxation, as an amateur, not knowing the current algorithms for decomposing a $2$-almost prime number $...
Stéphane Jaouen's user avatar
2 votes
0 answers
76 views

The process of doubling and removing zeroes and the number $234,715, 136$

Recently, i've been experimenting. What i would do is double the number, then remove the 0s in its digits, then repeat. There's lots and lots of cycles but i stumble a particularly long one. $$118, ...
Bryle Morga's user avatar
1 vote
0 answers
40 views

Squares of sum of digits of a number part 2

This is a sequel to my previous question which was this Squares of sum of digits of a number For those new I will give some context. Take a number then add up it's digits and square them then repeat ...
Aarush Saharan's user avatar
1 vote
0 answers
48 views

Sequences of the form $A(n) = A(A(n-1)\bmod n)^2$

$$A(0)= x \in\mathbb{Z}^+,\ A(n) = A(A(n-1) \bmod n)^2$$ At first glance, one would think that such sequence would grow very fast. But my testing suggest that this sequence actually ends with $x^4$ ...
Bryle Morga's user avatar
1 vote
0 answers
77 views

Consecutive numbers

Are there ever more consecutive composite numbers than there are primes up to that point? I imagine not, because the primes are the ones which cancel out multiples, so will inevitably have to fill in ...
Talon Eaglefeathers's user avatar
2 votes
0 answers
68 views

Behaviour of $a^k\pmod b,\ k=1,2,3,\ldots$

Let $n\in\mathbb{N}.$ Suppose $\left(x_k\right)_{k=1}^{n}$ is a $k-$tuple of $-1$'s and $1$'s. Let (the function) $r(i,j)$ be the remainder when $i$ is divided by $j,$ so that $0\leq r(i,j) \leq j-1.$ ...
Adam Rubinson's user avatar
1 vote
0 answers
47 views

Positive solutions to a linear Diophantine equation

Let $d,d',n\in \mathbb N$ be given. If you want, assume $(d,d')=1$. How many positive integer solutions does $$dx+d'x'=n$$ have? (Assuming $(d,d')=1$). I know there are $n/dd'+\mathcal O(1)$ solutions,...
tomos's user avatar
  • 1,682
3 votes
1 answer
67 views

A question on AOPS from AMC 12 left without a solution.

So I was doing some math questions on AOPS when i stumbled across this question which did not have a solution for it. I really want to know the solution to this problem so please help me. 2002 AMC 12P ...
Shaurya Shrimal's user avatar
2 votes
1 answer
83 views

Finding the 123ʳᵈ Number in a Sequence After Removing Multiples of 5 or 7

I'm working on a problem involving a sequence of the first 300 positive integers, from 1 to 300. However, I need to find the 123ʳᵈ number in the sequence after removing all numbers that are divisible ...
My Car's user avatar
  • 162
5 votes
0 answers
88 views

Is this a legitimate method of finding another prime number? [duplicate]

My motivation for asking this question stems from Euclid's elegantly simple proof of the infinitude of prime numbers. I am not suggesting an alternative proof, since my method, even if is valid, ...
user1153980's user avatar
  • 1,121
-1 votes
0 answers
33 views

GCD of $\frac{a^p + b^p}{a + b}$ and $a + b$ where p is an odd prime [duplicate]

The question is to find the GCD of $\frac{a^p+b^p}{a+b}$ and $a+b$ where p is an odd prime, in two cases, when $p|(a+b)$ and when it doesn't. I found, through several examples, that in the first case ...
Zaid's user avatar
  • 9
3 votes
0 answers
84 views

How do you multiply in Primorial number system?

Primorial number system is a number sytem that uses primorials which are defined as follows : Let $p_1=2, p_2=3,p_3=5,p_4=7,p_5=11,...$ the primes. The sequence of primorials, noted $p_n\#$ is $$(p_n\#...
Stéphane Jaouen's user avatar

1
2 3 4 5
750