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.

learn more… | top users | synonyms (1)

0
votes
0answers
27 views

Deducing Lindemann-Weierstrass from Baker's theorem

I'm aware that Baker's theorem with $n=1$ (for one algebraic number only) follows from that of Lindemann-Weierstrass. It is also often mentioned that Baker's result is a generalization of Lindemann-...
0
votes
2answers
68 views

Find the first digit of a number

I have seen this question but i could not find any answers.Let A= a*b*c*d.... very huge multiplication So what we can do take ...
1
vote
0answers
76 views

Theorem 3.3 Apostol's Analytic Number Theory

The below texts are from the book Introduction to Analytic Number Theory by Apostol: Note. Part (d) Thm 3.2 [green-underlined] is $$\sum_{n\le x}n^a=\dfrac{x^{a+1}}{a+1} +O(x^a) \ \ \text{if} \ a\...
2
votes
1answer
75 views

Symmetric sums in a magic square

Numbers $1,2,\ldots,16$ are written in a $4 \times 4$ square matrix so that the sum of the numbers in every row, every column, and every diagonal is the same and furthermore that the numbers $1$ and $...
3
votes
1answer
52 views

On the proof of Lucas' theorem

Lucas theorem states that Let $m,n$ be two natural numbers, $p$ be a prime. Suppose that $m, n$ admit the following base $p$ representation $$m=m_0+m_1p+\cdots+m_sp^s,\qquad n=n_0+n_1p+\cdots+n_sp^...
0
votes
1answer
14 views

How to design a threshold function without using any comparison operator?

What are some methods to design a function that outputs $1$ if the input value $x$ is greater than a threshold $T$ and $0$ otherwise. $f(x,T)=\begin{cases} 1,x\geq T\\ 0, x<T \end{cases}$
2
votes
0answers
44 views

Usefulness of largest known prime [duplicate]

Does it make sense to keep track of largest known prime? In other words: Are there any (more or less practical) situations, where we need the largest known prime? (except of the "situation" of ...
0
votes
0answers
37 views

On Pohlig-Hellman prime power discrete logarithm algorithm

If $p,q$ are odd primes and suppose we know $x\bmod 2^rp^tq^u$ in $g^x=h\bmod q$ where $2^{r+1}p^{t+1}q^{u+1}|\phi(q)$ and $g$ generates $\Bbb Z_{n}^\times$ then what is the procedure and complexity ...
7
votes
0answers
206 views

Find all values of $n \in \mathbb{N}$ for which the fraction $\frac{3^n-2}{2^n-3}$ is reducible [duplicate]

Find all values of $n \in \mathbb{N}$ for which the fraction $\frac{3^n-2}{2^n-3}$ is reducible. Attempt: We find all values of $n$ for which $\gcd(3^n-2,2^n-3)=1$ and take the complement. Since $2^...
1
vote
1answer
24 views

A question on divisibility of binomial coefficient

In this paper, page 3, theorem 4, the author claimed that If $m, n, k$ are three positive integer such that $\text{gcd}(n, k)=1$ then $\binom{mn}{k}\equiv 0\pmod n$. And he proved it as ...
1
vote
1answer
35 views

Binary expansion

The ternary expansion $x = 0.10101010\ldots$ is given. Give the binary expansion of $x$. Alternatively, transform the binary expansion $y = 0.110110110\ldots$ into a ternary expansion. By the ...
5
votes
3answers
61 views

$x^2$ modulo a prime

Prove that $x^2$ modulo a prime $p>2$ takes on exactly $\dfrac{p+1}{2}$ different values. I thought of first saying the residues modulo $p$ can be written as follows: $$0,1,\ldots,\frac{p+1}{2}-1,...
0
votes
1answer
39 views

Lists of primitive congruent numbers

Can anyone provide me with a reference to lists of primitive congruent numbers that are greater than $10^4$?
2
votes
1answer
34 views

Does $1$ or $2$ come first in the sequence $i + k, i + 2k, i + 3k…$ modulo $n$?

Given coprime numbers $k$ and $n$, we can take any number $i$ and keep adding $k$ to it until we reach a number which is congruent to either $1$ or $2$ modulo $n$. This classifies the numbers between $...
1
vote
1answer
22 views

Proving the complete additivity of the Big Omega function $\Omega(n)$ (total number of prime factors of n) .

The Big Omega function $\Omega(n)$ gives you the total number of prime factors of the number n. A function $f(x)$ is completely additive if $f(ab)=f(a)+f(b)$ for all positive numbers $a$ and $b$, ...
-1
votes
0answers
55 views

A square-related question in modular arithmetic…

Let $n$ and $k<\frac{n}{2}$ be integers with $4|n$. Find the pairs $(n,k)$, such that: $i(k-1)\not\equiv\frac{n}{2}\pmod n$, for all $i\in\mathbb{Z}_n$, or $i(k+1)\not\equiv\frac{n}{2}\pmod n$, ...
0
votes
2answers
111 views

Does there exist such a number?

Does there exist a $2n$-digit number $\overline{a_{2n}a_{2n-1}\ldots a_1}$ (for an arbitrary $n$) for which the following equality holds: $$\overline{a_{2n}\ldots a_1}= (\overline{a_n \ldots a_1})^2?...
0
votes
0answers
31 views

A sequence contains two numbers congruent modulo $(10^{\beta}-1)m$

Let $\beta \geq 1$ be an integer and $m$ be an integer relatively prime to $10$. Prove that the sequence $1,10^{\beta},10^{2\beta},\ldots$ contains two numbers congruent modulo $(10^{\beta}-1)m$ and ...
2
votes
2answers
43 views

How to find the class number of $\mathbb{Q}(\sqrt{-17})$?

I tried to calculate the class number with help of the Minkowski bound of $M \approx 5$. So if an ideal has norm $1$, it is the ring of integers. If it has norm $2$, it is $(2, 1+\sqrt{-17})$, which ...
0
votes
0answers
23 views

Embeddings of $K_v$ in $\mathbb{C}$

Let $K$ be a number field, $v$ a nonarchimedean prime, and $K_v$ the completion of $K$ at $v$. We have the embedding $K \to K_v$, and also $K \to \mathbb{C}$. I have two related questions: Is ...
-1
votes
1answer
56 views

Given $N$ find the number of natural numbers less than $N$ that may be written in the form $\frac{(k)(k+1)}{2}$

Given $N$, find the number of natural numbers less than $N$ that may be written in the form $$\frac{k(k+1)}{2},$$ where $k\in \Bbb N$. I know that the answer to this problem is approximately $\sqrt {...
2
votes
1answer
81 views

Finding the value of a sum over all the subsets of a given set

Given a sequence $A = \{a_1,a_2,a_3,\ldots,a_n\}$ we have to find the ...
-1
votes
0answers
28 views

Confusion between Sequences and Number theoretic functions.

I've just started learning Number Theoretic function,the definition of ,Number Theoretic function,which i've just read created some confusion b/w Number Theoretic function & Sequences. The ...
1
vote
2answers
68 views

Finding all possible values of a Function

Let a function be defined as $f:N\to N$ and $x-f(x)= 19\left[\dfrac{x}{19}\right] - 90\left[\dfrac{f(x)}{90}\right] \forall x\in \Bbb N$ and $1900<f(1990)<2000$. Find all values of $f(1990)$. $...
0
votes
1answer
36 views

Isogenic elliptic curves. Number of points and zeta function

Is there any book or other reference where I can find a complete proof of the following fact? If $E$ and $E'$ are two isogenic curves (over $\mathbb{F}_q$, where $q=p^a$), then for any $n \ge 1$ the ...
2
votes
2answers
34 views

Quadratic equation solutions modulo prime p

the question is: find all primes p that satisfy the equation: x^2-2*x-5 = 0 (mod p) The discriminante is 24, and I know that the equation mod p has a solution ...
1
vote
1answer
49 views

A set $S$ of all the different odd positive integers

Consider the set $S$ of all the different odd positive integers that are not multiples of $5$ and that are less than $30m$, $m$ being a positive integer. What is the smallest integer $k$ such that in ...
0
votes
1answer
20 views

A detail on the proof of equivalence of valuations

I have trouble understanding a step of Neukirch's proof of the characterization of equivalent valuations. The step is Now let $y \in K$ be a fixed element satistying $|y|_1>1$. Let $x\in K$, $...
2
votes
1answer
26 views

Groups with order a product of unrelated distinct primes

Consider a group of size $n$, where $n$ is the product of distinct unrelated primes (two primes $p$ and $q$ are unrelated if $q \nmid (p-1)$ and $p \nmid (q-1)$). The claim is that there is only one ...
1
vote
2answers
96 views

Solutions to $[x^2]+2[x]=3x\text{ where } 0\le x\le 2$

Find all solutions to $$[x^2]+2[x]=3x\text{ where } 0\le x\le 2$$ and $[x]=\lfloor x\rfloor$ $$$$ I managed to simplify this to $[x^2]-[x]=3\{x\}$. Thus, $$[x^2]-[x]=\{0,1,2\}$$ However I got ...
0
votes
1answer
30 views

Multiplicity of primes in factorial

Denote by $x_n(p)$ the multiplicity of the prime $p$ in the canonical representation of the number $n!$ as a product of primes. Prove that $\dfrac{x_n(p)}{n} < \dfrac{1}{p-1}$ and $\lim_{n \to \...
4
votes
1answer
61 views

The limit of consecutive positive integers which are the product of n primes.

The maximum length of a string of consecutive primes is 2: that is, the primes 2, 3. This is easily proven, as no even number other than 2 is prime. In contrast, consider the set of numbers which ...
2
votes
2answers
67 views

Prove that $\sin x=[1+\sin x]+[1-\cos x]$ has no solution in $x\in \Bbb R$

Prove that $$\sin x=[1+\sin x]+[1-\cos x]$$ has no solution for $x\in \Bbb R$ where $[x]=\lfloor x\rfloor$ $$$$I reduced the equation into $$\sin x=2+[\sin x]+[-\cos x]$$ From here, I plotted ...
2
votes
2answers
31 views

Use of greatest common divisor to calculate unknown

We have three numbers $x ,y, z$. If we know the values of $x$ and $z$ then is it correct to say that $y$ should be a multiple of $z/\gcd(z,x)$ for the expression shown below to be true? Here $\gcd$ ...
3
votes
1answer
80 views

Number of primes less than or equal to $n$

Let $\nu (n)$ be the number of primes less than or equal to $n$ where $n$ is a positive integer. Prove that $\dfrac{n}{\nu(n)}=k$ has a solution for every integer $k \geq 2$. I was thinking of using ...
1
vote
3answers
55 views

Solutions to $\{x^3\}+\lfloor x^4\rfloor=1$

Find all solutions of $$\{x^3\}+[x^4]=1$$ where $[x]=\lfloor x\rfloor$ $$$$ I know that $0\le\{x^3\}<1\Rightarrow 0<[x^4]\le 1$. Thus $[x^4]=1$. I couldn't get any further though since I'm ...
9
votes
6answers
204 views

Prove $\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{n+2}{4}\rfloor+\lfloor\frac{n+4}{8}\rfloor+\lfloor\frac{n+8}{16}\rfloor+ \dots=n$

Prove $$\left[\dfrac{n+1}{2}\right]+\left[\dfrac{n+2}{4}\right]+\left[\dfrac{n+4}{8}\right]+\left[\dfrac{n+8}{16}\right] + \dots=n$$ where $[x]=\lfloor x\rfloor$ $$$$ It was suggested that ...
3
votes
2answers
61 views

Origin of Almost Perfect Numbers

Let $N$ be a positive integer. $N$ is called a perfect number if the sum of its positive divisors denoted by $\sigma(N)=2N$. For example $6$ is a perfect number since: $\sigma(N)=1+2+3+6=12=2(6)$. ...
1
vote
2answers
84 views

Is this the correct way to compute the last $n$ digits of Graham's number?

For the following question, all what is needed to know about Graham's number is that it is a power tower with many many many $3's$ Consider the following pseudocode : input n Start with $s=1$ and $...
0
votes
2answers
67 views

Solutions to $\lfloor 2x\rfloor-\lfloor x+1\rfloor=2x$

Find all solutions to $$[2x]-[x+1]=2x$$ where $[x]=\lfloor x\rfloor$ $$$$ I divided this into 2 cases: $$Case 1:x=[x]+\{x\}\text{ where } 0\le\{x\}<0.5$$ $$Case 1:x=[x]+\{x\}\text{ where } 0.5\...
4
votes
2answers
127 views

Solutions to $\dfrac{1}{\lfloor x\rfloor}+\dfrac{1}{\lfloor 2x\rfloor}=\{x\}+\dfrac{1}{3}$

Find all solutions to $$\dfrac{1}{\lfloor x\rfloor}+\dfrac{1}{\lfloor 2x\rfloor}=\{x\}+\dfrac{1}{3}$$ $$$$ Unfortunately I have no idea as to how to go about this. On rearranging, I got $$3\lfloor ...
2
votes
1answer
54 views

Proof of Lagrange's four square theorem using Cauchy-Davenport Theorem

Cauchy used the Cauchy-Davenport theorem to prove that $ax^2 + by^2 + c \equiv 0 \pmod p$ has solutions provided that $abc \neq 0$. Lagrange used this result to establish his four squares theorem. I ...
0
votes
0answers
47 views

Harmonic Denominator Not Divisible by $3$

This is in relation to my previous question Dividing Harmonic Number's Denominator. The answer there says that they "found no $H_n$ with denominator not divisibly by 3 for $68<n\le 10000$. How ...
1
vote
1answer
36 views

Cyclic prime groups

can I have a refrence to an introduction (not super beginner level, one after) of the multiplicative group $Z/ZP$? I know that it is cyclic. I am interested in known properties of the generators. ...
5
votes
4answers
200 views

Does $8a+5$ ever divide $b^2+8$?

For natural $a,b$, does $8a+5$ ever divide $b^2+8$ ? It doesn't for $b$ up to $10^7$. Couldn't find congruence obstructions for moduli up to $500$. $b^2+8$ can be even.
1
vote
2answers
35 views

Finding unknown numbers using $ LCM $ and $ HCF $

Find two numbers, $A$ and $B$, both smaller than $100$, that have a lowest common multiple of $450$ and a highest common factor of $15$. I know that this involves the formula of $A × B = LCM × HCF$ ...
3
votes
4answers
80 views

Bound for the sum of the divisors of a number

Let us denote by $s(n) = \sum_{d|n} d$ the sum of divisors of a natural number $n$ ($1$ and $n$ included). If $n$ has at most $5$ distinct prime divisors, prove that $s(n) < \dfrac{77}{16}n$. Also ...
1
vote
1answer
107 views

A question about the existence of

Maybe a stupid question: Let $p_1,p_2,p_3$ be prime numbers and $0\leq x_1<p_2$, $0\leq x_2<p_1$,$0\leq x_3<p_3$. If $x_1$ is fixed, is there exist such $x_2,x_3$ satisfying that $x_1p_1+...
2
votes
1answer
78 views

Is there any formula to calculate the number of different Pythagorean triangle with a hypotenuse length $n$, using its prime decomposition?

Lets define $N(n)$ to be the number of different Pythagorean triangles with hypotenuse length equal to $n$. One would see that for prime number $p$, where $p=2$ or $p\equiv 3 \pmod 4$, $N(p)=0$ also $...
12
votes
2answers
1k views

Why can no prime number appear as the length of a hypotenuse in more than one Pythagorean triangle?

Why is it that no prime number can appear as the length of a hypotenuse in more than one Pythagorean triangle? In other words, could any of you give me a algebraic proof for the following? Given ...