Questions tagged [number-theory]

Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

Filter by
Sorted by
Tagged with
0
votes
0answers
4 views

Are there techniques for quickly seeing patterns in numbers?

Recently I was watching 8 out of 10 cats does countdown (S18E01 - 26 July 2019), for which the math question there was the following numbers: if you haven't seen countdown, you are provided 6 numbers,...
1
vote
1answer
40 views

Question on odd positive integers and Fermat factors

Let $n$ be an odd positive integer, Let $o=\operatorname{ord}_n 2$ be the order of 2 modulo $n$ and $m$ the period of $1/n, k$ is number of distinct odd residues contained in set $\{2^1,2^2,...,2^{n−1}...
-2
votes
0answers
6 views

Let n be a natural number with the prime decomposition n = p1^s1 + p2^s2 + … + pk^sk [duplicate]

Prove that if n = m^2 for some natural number m then s1, s2, . . . , sk are all even.
0
votes
0answers
15 views

Numeric functions

Let $n$ and $k$ be positive integers. A function $f$:{$1, 2, 3, 4, ... kn$} --> {$1, ... 5$} is said to be good if $f (j + k) - f (j)$ is a multiple of $k$ for all $j = 1.2, ..., kn - k$ a) Prove ...
8
votes
1answer
95 views

A comment in the Disquisitiones Arithmeticae

Gauss proves that if $t\equiv\pm 3\mod 8$, then $2$ is a non-(quadratic)-residue modulo $t$ as follows: Assume $t\equiv\pm 3\mod 8$ is the smallest counter-example, and say $a^2\equiv 2\mod t$, ...
1
vote
1answer
42 views

Polynomial whose roots are some of the Nth-roots of unity.

I have to compute the following quantity \begin{align} \prod_{\alpha\neq\beta=0}^{N-1} \left(1-e^{2\pi i \frac{\alpha-\beta}{aN}}\right)\label{a}\tag{1} \end{align} where $a$ is a natural number, ...
3
votes
1answer
55 views

Solve discrete logarithm, $a^x = b \bmod 2^N$ by p-adic logarithm

I want to find the smallest solution, $x$, for $$a^x = b \bmod 2^N$$ by using p-adic logarithm. We suppose $a \bmod 4 =1$ and $b \bmod 4 = 1$. Another case can be solved easily or converted to $a, ...
0
votes
0answers
26 views

Find all solutions $(x, y, z)$ ∈ $\mathbb N^+ ×\mathbb N^+ ×\mathbb N^+$ for the following equations in $\mathbb Z$

Find all solutions $(x, y, z)$ ∈ $\mathbb N^+ ×\mathbb N^+ ×\mathbb N^+$ for the following equations in $\mathbb Z$: (a) $3x^2 + 4y^2 = z^2$ (b) $3x^2 + 6y^2 = z^2$ My attempt: a) If I ...
2
votes
1answer
58 views

Pairs of perfect squares

Two perfect squares are said to be friendly if one is obtained from the other by adding the digit 1 on the left. For example, $1225 = 35 ^ 2$ and $225 = 15 ^ 2$ are friendly. Prove that there are in ...
2
votes
0answers
50 views

Sum of the digits in base $p+1$

Definition Let $W$ be the function , defined as $W(a,b)=r$ given $a,b\in \mathbb{Z_+}$ and $a>1$ Take $m$ to be the integer s.t. $a^{m+1} \ge b > a^{m}$, i.e. $m = \...
-2
votes
1answer
137 views

Proof of Fermat's last theorem $h^n+k^n=N^n$ for $n=3$ and $N$ prime number

Proof of Fermat's last theorem $h^n+k^n=N^n$ for $n=3$ and $N$ prime number $h^3+k^3=[[h*(h+1)/2]^2-[h*(h-1)/2]^2]+[[k*(k+1)/2]^2-[k*(k-1)/2]^2]=(h+k)*(h^2-h*k+k^2)=N^3$ If $N$ is a prime number $(h^...
8
votes
2answers
82 views

Is there a perfect square (other than 9) all of whose digits are 7, 8, or 9?

Clearly, $3^2=9$ is a perfect square, all of whose digits are $7$, $8$, or $9$. Are there any other perfect squares with this property? This is an interesting question that does not seem to be ...
-1
votes
1answer
11 views

p is without a common factor of 100000.Prove that power of p decimal representation ends with numbers group 00001. [on hold]

p is without a common factor of 100000.Prove that power of p decimal representation ends with numbers group 00001. Also prove that every natural nubmer n exist natural number k, that k power of p ...
2
votes
1answer
43 views

More infinite nested square roots

Let us consider the following nested square root: $$A=\sqrt{b_1+\sqrt{b_2+ \sqrt{b_3+\cdots}} }.$$ Consider the following three cases: $b_k = k^2 + k -1 \Rightarrow A = 2.$ $b_k = (k+2)^4 - 4(k+2)^3+...
7
votes
3answers
229 views
+50

Show that $x^4-20200y^2=1$ has no solution in postive integers

Show that $x^4-20200y^2=1$ has no solution in postive integers. This topic is a question for the Chinese middle school students' mathematics competition today, so I think this problem has a simple ...
1
vote
1answer
27 views

For prime $p>5$ and positive integer $k<p$, show that the decimal expansion of $k/p$ consists of $p-1$ repeating decimal digits

Trying to prove: Let $p > 5$ be a prime and let $k$ be any positive integer $< p$. Show that the decimal expansion of $\frac{k}{p}$ consists of (p-1) repeating decimal digits. (hint: use ...
1
vote
1answer
68 views

Prove that there are infinitely many primes congruent to 3 modulo 4

I know this question has been asked, but I think I finally have the right proof after looking at the others. I am just confused with one part of the proof. I am confused on the part where "Any two ...
1
vote
1answer
20 views

What conditions must be met to make f(x) = a^x mod N periodic but not constant?

The renowned quantum algorithm Shor's Algorithm relies on the periodicity of the function $f(x)=a^x mod N$. The a, x, and N are all positive integers. By observation, we know the function is constant ...
1
vote
2answers
31 views

Learning about subsets

I have a set $A$ defined to be the power set P(X) where X is itself a nonempty set and that for the set $A$ and the relation $R$ on $A$ we have $$\forall(x,y) \in A \times A$$ $$\exists xRy$$ provided ...
1
vote
2answers
51 views

How can be proved $\sqrt{n^8+2\cdot 7^{m}+4}$ is irrational?

How can be proved $\sqrt{n^8+2\cdot 7^{m}+4}$ is irrational, where $n,m \in \mathbb{N}$. I tried to write: $$a^2-n^8=2(7^m+2)$$ and to try finding the last digit in the left and in the right side. ...
3
votes
1answer
30 views

function — minimum number of times you have to add two integers in your set, to reach a number n

Suppose you start with the set {1}. A "step" consists of adding a number in your set to another number in your set (or possibly the same number), and making the new number a part of your set. So the ...
0
votes
3answers
58 views

Let set A is subset of set $\{{1,2,3,…,100}\}$ which has $55$ different elements.

Let set $A \subset\{{1,2,3,...,100}\}$ with $55$ distinct elements. Prove that there exist two elements in $A$ which have a difference of 10. I understand that the common thing is that we take more ...
18
votes
4answers
2k views

Prove that the sum of digits of $(999…9)^{3}$ (cube of integer with $n$ digits $9$) is $18n$

Someone had posted a question on this site as to what would be sum of digits of $999999999999^3$ (twelve $9s$ ) equal to? I did some computation and found the pattern that sum of digits of $9^3 = ...
0
votes
1answer
33 views

When is $\sum_{n=0}^{4}{x^n},~\text{where}~x\in \mathbb{N}>0$ square? [duplicate]

When is $\sum_{n=0}^{4}{x^n}$ ($x$ a natural number greater $0$) square ? Any help would be appreciated.
0
votes
0answers
19 views

Cyclotomic $\mathbb{Z}_p$-extensions of number fields

Let $p$ be a fixed odd prime. Let $F/\mathbb{Q}$ be any number field which does not contain $\mu_p$. Consider the cyclotomic $\mathbb{Z}_p$-extension of $F$, this is the unique $\mathbb{Z}_p$-...
-1
votes
1answer
51 views

How many positive integer(s) x is / are there so that $\sqrt{x^2 + 4x + 670}$ is an integer? [on hold]

How many positive integer(s) x is / are there so that $\sqrt{x^2 + 4x + 670}$ is an integer? I can do it up till the completing the square portion. However, the (u+x+2)(u-x-2) messes me up.
1
vote
1answer
78 views

Asymptotics of the Atkin-Bernstein sieve on primes

I am working through the paper by Atkin and Bernstein, Prime sieves using binary quadratic forms, see https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ...
2
votes
0answers
46 views

Prove that the sequence is exact using universal property.

Denote by $\mathbb Z_p$ the ring of $p$-adic integers. Recall that $\mathbb Z_p$ can be interpreted algebraically as the inverse limit of the directed system $$...\mathbb Z/p^n\mathbb Z\to \mathbb Z/p^...
1
vote
1answer
24 views

The converse of Hensel's lemma

I know the following version of Hensel's Lemma. Hensel's Lemma: Suppose $p$ is an odd prime, $a \not \equiv 0 \pmod p$ and $j > \ge 1$. If we have a solution $x_j$ to the equation $$a \...
-1
votes
0answers
41 views

How to show that no function f from Z to Z satisfies f(f(x)) = x + 5? [duplicate]

Question pretty much explains it. So far I can show that f(x + 5) = f(x) + 5 but I don't know where to go from there.
-5
votes
1answer
46 views

Check whether or not a given number N is triangular number [on hold]

I'm trying to write a program that would tell me wether or not a number N is triangular number. Any formula exists for this ?
7
votes
1answer
77 views

A Diophantine Equation related to arithmetic progression: $T_n=a^n+b^n+c^n$.

I'm working on a problem that for complex $a,b,c$, when will these four numbers $a+b+c, a^2+b^2+c^2, a^3+b^3+c^3, a^4+b^4+c^4$ becomes an arithmetic progression with integer values. If we let this ...
1
vote
2answers
31 views

Bound on the sum of squares of the number of divisors until $Z$ (Vaughan Circle method)

I was wondering how I could show that $\displaystyle \sum_{x\leq Z}d(x)^2\ll Z(\log 2Z)^3$, where $d(x)$ counts the number of divisors of $x$. I tried to prove this in the following fashion (and ...
2
votes
1answer
115 views

Does $n^r\equiv n\pmod{10^a}$ imply $n^2\equiv n\pmod {10^a}$ for all natural numbers $n$ and $a$?

If $r$ is odd and $n\equiv-1\pmod {10^a}$ then $n^r\equiv n\pmod{10^a}$ but $n^2\not\equiv n\pmod{10^a}$. If $r$ is even, then for $r=2$ this is clearly true, but I found that for $r=6$, $16^6\...
0
votes
0answers
20 views

Comparison of Strong vs Extra Strong Lucas probable prime

The extra strong Lucas probable prime test seems to have more pseudo primes (i.e. composite numbers that it detects as primes) than the strong Lucas probable prime test. From OEIS the first 5 extra ...
1
vote
1answer
37 views

Gcd of two number divides each other [duplicate]

(a) Prove that $\operatorname{gcd}(a, b) | \operatorname{gcd}\left(3 a+b, a^{3}\right)$ Since say $d = gcd(a,b)$ then $d|a$ and $d|b$ this will imply $d|(3a+b)$ and $d|a^3$ and therfore $d$ is ...
0
votes
2answers
41 views

Non linear Diophantine Equation

Can anyone please tell me a general method to solve non-linear Diophantine equation like $8^x + 15^y=17^z$ $x^3 + 2y^3 = 4z^3$
0
votes
0answers
35 views

Question on function similar to the sigma function

If $d_1,d_2,d_3, \ldots, d_k$ are divisors of $n$ such that $d_1<d_2<d_3 < \cdots <d_k$ then what is $$ \sum_{i=2}^k i\cdot d_i$$ I'm trying to see if this has a closed form or any kind of ...
3
votes
1answer
26 views

Jacobi Symbol: $\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$

Show that if $p$ is and odd prime and $h$ is an integer, $1\le h \le p$, then $$\displaystyle\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$$ where $\left(\frac{m+n}...
8
votes
1answer
617 views
+50

Prime factor $>250000$ for $1002004008016032$

I need to find a prime factor, $p$, of $1002004008016032$ such that $p \gt 250000$. Now this is a very large number and I know it would be stupid of me to factorize such a large number into its prime ...
0
votes
0answers
32 views

Jacobi Symbol: $\sum_{n=1}^{n=p}\left(\frac{n^2+a}{p}\right)=-1$

Show that if $(a,p)=1$, $p$ an odd prime then, $\sum_{n=1}^{n=p}\left(\frac{n^2+a}{p}\right)=-1$, where $\left(\frac{n^2+a}{p}\right)$ is the Jacobi symbol. This question has been taken from the book ...
1
vote
1answer
18 views

Calculating Legendre symbol : $\left(\frac{3}{2^{2^n}+1}\right)$ , n being positive.

I want to find the Legendre symbol : $\left(\frac{3}{2^{2^n}+1}\right)$ for any positive n. Also I want to find the Legendre symbol for: $\left(\frac{5}{2^{2^n}+1}\right)$, when $n>1$ Solution: ...
1
vote
1answer
33 views

Find the common factor given a series of numbers

Let $r$ be an integer that $1<r<2^n$. We are given a series of $k$ integers of the following form: $\left[s_1\frac{2^n}{r}\right], \left[s_2\frac{2^n}{r}\right], \ldots, \left[s_k\frac{2^n}{r}\...
0
votes
2answers
31 views

Suppose f is a multiplicative function such that, for odd primes p, f(p) = 3p

How would one go about this question? I am unsure of what to do. Would you do for f(11) f(11)= f(8)+f(p), where p=1 f(11)= 9x3(1) = 27
-1
votes
0answers
18 views

Counting the set of representatives $\Gamma_0(N) \backslash \Gamma(1)$

I have a question about counting the size of set of representatives $\Gamma_0(N) \backslash \Gamma(1) $ which boils down to the following elementary number theory problem: Let $S:=\{\{c,d\}:\gcd(c,...
1
vote
0answers
38 views

Question about semi-twin primes

Has anyone ever studied the following numbers? I came up with the name semi-twin primes as I could not find any reference on this topic. These are prime numbers $p$ such that $p+1 = 2q$, with $q$ ...
0
votes
2answers
26 views

Minimum number of points to win a football league

Let $n$ be the number of teams in a football league. $n$ is even. Each pair of teams plays each other $2$ times (home and away) during the season. There are $2(n-1)$ fixtures and in each fixture there ...
5
votes
2answers
262 views

what is formula for $\sum_{i=0}^{b-1} (-1)^{i}(b-i)^{m}\binom{b-1}i$ and Real Roots Polynomials

Definition let $b$ and $m$ are non negative integers with $b\ge 1$ $$D_{m,b}=\sum_{i=0}^{b-1} (-1)^{i}(b-i)^{m}\binom{b-1}i$$ I observed $$D_{m,m+1}=m!$$ $$D_{m,m}=(m+1)!/2$$ $$D_{m,m-1}= (m+1)...
3
votes
1answer
37 views

What's the expectation of the number of times of a loop being fully covered

Consider a loop with a length of 1, then randomly select a continuous part on this loop with a length of 0.5 and cover it. Repeat this process for k times until the loop was fully covered. Find the ...
1
vote
0answers
22 views

Successive minima

Definition: The $n$ successive minima $\lambda_1,..,\lambda_n$ of $C$ with respect to lattice $L$ are defined as follow $\lambda_i$ is the minimum of all positive reals $\lambda$ such that $\lambda C ...