Questions on more advanced topics of number theory. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

1
vote
1answer
17 views

What is the probability that a random K-bit odd-number is prime?

Is it $e/K$? In an experiment that created 1000 random RSA-2048 key-pairs, 2000 random 1024-bit primes were created. It turned out that $727,709$ random candidates were generated, to create 2000 ...
2
votes
1answer
17 views

Suggestion to a book about number theory

What I am looking for is a book that contains "infinitely many problems", starts from the easiest to high level(that can be found in national and even international olympiads). Are there such books, ...
1
vote
0answers
22 views

Generalizing in Mathematics

I was reading the book "Fermat's Last Theorem" by Simon Singh when it hit me that this theorem is so contrived, andyet it lead to several important breakthroughs in mathematics and especially the ...
0
votes
0answers
17 views

Continued fraction approximation

Let $\theta\in\Bbb{R}_{\gt0}$. A) Prove that the convergents for the continued fraction expansion of $\theta$ give us better and better rational approximations to $\theta$. B) Suppose $\theta\notin ...
2
votes
2answers
25 views

a root of some polynomial over finite field

I think this is a really basic question, but it had been a little while since I dealt with this material and I was hoping to get a bit of assistance here. Let $q = p ^{2M}$ for some prime $p$ and $M ...
0
votes
0answers
15 views

Idele for a rational number q=63/550 .

Wikipedia, in its article "p-adic number", has taken an arbitray number x=63/550 to show the p-adic absolute value with respect to different primes. Obviously, the p-adic absolute value is 1 for ...
0
votes
1answer
13 views

solve $k(k-1) \geq \ln2*2m$ for k

My Question is related to the birthday problem. Starting at $e^{-\frac{k(k-1)}{2m}} \leq 0.5$ i used $ln(x)$ on both sides and multiplied by $-2m$ to get $k(k-1) \geq \ln2*2m$ According to my ...
0
votes
1answer
47 views

The diophantine equation $a^7+b^7=7^c$

Determine all the triples of positive integers $a,b,c$ such that $a^7+b^7=7^c$.
1
vote
1answer
27 views

If $a+bi$ is in $E_k$ then $a-bi$ is also in $E_k$?

I'm currently studying the properties of the Motzkin sets $E_k$, $k\in\mathbb{N}\cup\{0\}$ of the ring $\mathbb{Z}[i]$. The definition of $E_k$ is as follows: $E_0=\{0\}$, $E_1=$units of ...
0
votes
2answers
37 views

Understanding why the public exponent $e$ is chosen the way it is in RSA

I am trying to get a better understanding of RSA. At the moment I am unable to understand the difference between the correctly chosen value of the public exponent $e$ and other possibilities ...
1
vote
0answers
18 views

Transforming the cubic Pell-type equation for the tribonacci numbers

The Lucas and Fibonacci numbers solve the Pell equation, $$L_n^2-5F_n^2=4(-1)^n\tag1$$ The tribonacci numbers $z = T_n$ are positive integer solutions to the cubic Pell-type equation, $$27 x^3 - 36 ...
2
votes
2answers
37 views

Solving Linear Congruences With The Euler Totient Functio

I've been asked to calcualte $15^{123456789012345}$ mod $2500$. Now I worked out $\varphi(2500)=1000$ but I can't use Euler's theorem here because $1000$ and $2500$ aren't coprime. Can anyone offer ...
1
vote
1answer
48 views

Every element of field $F_q$ has $k$th root if and only if $\gcd(q-1,k)=1$

Help me please to prove that: For any $k \in \mathbb{N}$ each element of field $F_q$ is the $k$-th power of some element from that field if and only if $GCD(q-1, k)=1$. My approach Let's look ...
1
vote
1answer
29 views

Solving Linear Congruences With Euler Totient Function

I've been asked to solve the following congruence $x^{1667}\equiv2$ $mod$ $2500$. Am I right in saying there's no solution modulo 2500 to this congruence since even though 1667 is coprime to ...
0
votes
0answers
25 views

Polynomial/ Exponential diophantine equation

I am looking for the reference characterizing all the cases when $$an^2+bn+c=2^m$$ has infinitely many positive integer solutions (m,n). Thanks.
3
votes
1answer
34 views

Solving A Certain Diophantine Equation

I am stack on finding the solution of the diophantine equation: $d(2^{k+1}-1)-b^2(2^{k+1}-2)=1$. where $k\geq 1$ and $b^2>d$ for $b$ an odd composite integer. Is there a solution to this ...
0
votes
0answers
30 views

Number theory and Group theory [on hold]

Can you give me any task which contains Number theory and Group theory?
8
votes
2answers
87 views

A number $N$ is a $k$-nacci number if and only if …

For $k\ge 2\in\mathbb N$, one can define the $n$-th $k$-nacci number $f_k(n)\ (n=0,1,\cdots)$ as $$f_k(0)=f_k(1)=\cdots=f_{k}(k-2)=0,\ \ ...
1
vote
0answers
26 views

e Online source for alternative proofs

I'm looking for some alternative proofs for various theorems. My goal is to compile a list of various proofs each relating to a specific theorem (such as the triangle inequality, Fermat's Little ...
2
votes
3answers
87 views

Collatz conjecture: Largest number in sequence with starting number n

This question is inspired by a CS course, and it only tangentially relates to the actual content of the exercise. Say in a hailstone sequence (Collatz conjecture) you start with a number n. For any ...
1
vote
1answer
37 views

All possible number combinations in decimal represenation of irrational numbers?

This question is directly inspired by "Does Pi contain all possible number combinations?". I would like to state firstly for the record that I have no serious number theory education. I think I ...
3
votes
1answer
27 views

Asymptotic formula for sums of powers of reciprocals of primes

Is there an explicit asymptotic formula, in terms of $\alpha$, for the expression $$\displaystyle \sum_{p \leq x} \frac{1}{p^\alpha}$$ for $0 < \alpha < 1$? The case $\alpha = 1$ is supplied by ...
1
vote
0answers
25 views

On a congruence for the number of finite topologies

I am making search about "On a congruence for the number of finite topologies". I have found a paper. I guess it is written in Russian. How can I find English version of this paper ? I am also ...
3
votes
1answer
30 views

Origin of period function model of primes

There is a web page attributed to Omar Pol, "Sobre el patrón de los números primos: Determinación geométrica de los números primos y perfectos." ("On the pattern of primes: Geometric Determination of ...
1
vote
1answer
45 views

What books do you recommend on mathematics behind cryptography?

I am currently reading the Book Understanding Cryptography from Cristof Paar. I am enjoying the book but i don't like to scratch the surface when it comes to cryptography. I would like do dig a little ...
11
votes
1answer
99 views

Are $121$ and $400$ the only perfect squares of the form $\sum\limits_{k=0}^{n}p^k$?

I've been looking for perfect squares that can be represented as $\sum\limits_{k=0}^{n}p^k$. Of course, both $n$ and $p$ should be natural numbers larger than $1$. Searching up to $n=100$ and ...
0
votes
0answers
15 views

How to expand powers of multiple pairwise commuting elements in a group [on hold]

Let (G, $\ast$) be a group and let n $\in\aleph$. Prove that if $g_1,...,g_k\in G, k\in\aleph$ are pairwise commuting elements of G, then $(g_1\ast...\ast g_k)^n$=$g_1^n\ast ...\ast g_k^n$
1
vote
1answer
23 views

Proofed: Every number in the sequence of powers of 2 have $phi = 1/2 * 2^x$

I want to know if it's proofed, that every number which is in the number sequence of the powers of $2$ has an $\phi$ of $\frac12x$.
1
vote
1answer
58 views

Induction proof involving Euler Totient Function

Let $\varphi$ be the Euler totient function Qi) show that if $r$ is a power of a prime number then $\sum_{d|r} \varphi(d) = r.$ Qii) Show that if $n \geq 2$ then there is a decomposition of n as a ...
1
vote
0answers
16 views

Understanding how to estimate $\pi(x)$ based on Paul Erdos's proof of Bertrand's Postulate

I am reading the 4th Edition of Proofs from the Book. I am not clear on how the proof behind Bertrand's postulate leads to the following statement on page 10 (of my edition): From (2) one can ...
2
votes
0answers
24 views

Nebentypus of contragredient representation

Let $k$ be a local non-archimedean field with ring of integers $\cal O$ and maximal ideal $\frak p$. Let $\pi$ be an irreducible admissible $\infty$-dimensional representation of $\text{GL}_2(k)$ ...
5
votes
1answer
73 views

The number of divisors of a number whose sum of divisors is a perfect square

Let $n$ denote a non-prime whose sum of divisors is a perfect square. I have noticed a few surprising facts on the number of divisors of $n$: It is either prime or semi-prime or $27$ in all cases ...
1
vote
0answers
31 views

Clever use of Pell's equation

Find infinitely many triples $(a,b,c)$ of positive integers such that $a,b,c$ are in arithmetic progression and such that $ab+1$, $bc+1$, and $ca+1$are perfect squares. The solution is: Consider the ...
1
vote
0answers
29 views

Strict total ordering

I'm not able to understand how the below relation is example of "strict total order". Consider a set $X = 2^Y$ where $Y = \{1,2,3,4,5,6,7,8,9\}$. The expected order of $X$ is for all $x, y$ ...
4
votes
0answers
70 views

Are there infinitely many $N^3$ (especially for prime $N$) that cannot be expressed as a sum of three positive cubes?"

Well few days ago i asked a question on perfect numbers and Tito Piezas III answered the question in a very intriguing way which has helped me to get a lead on it.But his answer and perfect numbers ...
4
votes
1answer
41 views

Two question about ${\mathbb Q}(\alpha)$ for $\alpha$ := $\sqrt[n]{7}$ + $\sqrt[n+3]{7}$

Let $\alpha$ = $\sqrt[n]{7}$ + $\sqrt[n+3]{7}$ with $n$ not divisible by $3$. Prove that $[{\mathbb Q}(\alpha) : {\mathbb Q}] = n(n + 3)$. Conclude that $\alpha$ is constructible if and only if $n = ...
4
votes
1answer
81 views

Trying to understand a step in Ramanujan's Proof of Bertrand's Postulate regarding the gamma function

My question relates to this step in the proof here: But it is easy to see that $$\log \Gamma(x)-2\log\Gamma(\frac12x+\frac12) \le \log\left\lfloor ...
2
votes
1answer
62 views

Multiples of 3 and 5. [on hold]

If we have the Tartaglia(Pascal) triangle in every row which numers are multiples of 3 which are even and which are multiples of 5?
1
vote
1answer
22 views

Understanding Bézout's identity

I'm trying to understand a proof of Bézout's identity ($gcd(a,b)=$ smallest linear combination of $a$ and $b$), and I'm having some trouble following the last step. The proof goes by: Let $m=sa+tb$ ...
1
vote
2answers
35 views

Is there a subset of natural numbers with a special property

Let set $A$ be an infinite big subset of the set $\mathbb{N}$ (set of natural numbers),it is not equal to $\mathbb{N}$ and it has the following property: For every $a$ that is not from the set $A$ ...
1
vote
1answer
26 views

How to solve second order congruence equation if modulo is not a prime number

the equation is $x^2 = 57 \pmod{64}$ I know how to solve equations like (*) $ax^2 +bx +c = 0 \pmod{p}$, where $p$ is prime and i know all the definitions for like Legendre's Symbol and all of the ...
0
votes
1answer
12 views

Partition of fractional parts where each sum of them has to be at least 1

Let $ a_1,\ldots,a_t \in \mathbb{Q} \setminus \mathbb{Z} $ be with $ \sum_{i=1}^t \lbrace a_i \rbrace \in \left[k,k+1\right) $ for some $ k \in \mathbb{N} $ with $ k \ge 4 $. Here $ \lbrace x \rbrace ...
4
votes
1answer
38 views

Integer solutions to a two variable equation.

For $m, n \in \mathbb{Z}$, show the only integer solutions to $f(m,n) = \displaystyle \frac{3^m(2^n+1)-2^{m+n}}{2^{m+n}-3^{m+1}}$ are $f(1, 2) = -7$, $f(0, 1) = -1$, and $f(0, 2) = 1$. More ...
6
votes
1answer
171 views

Can the cube of every perfect number be written as the sum of three cubes?

I found an amazing conjecture: the cube of every perfect number can be written as the sum of three positive cubes. The equation is $$x^3+y^3+z^3=\sigma^3$$ where $\sigma$ is a perfectnumber (well it ...
5
votes
0answers
62 views

Which prime gaps are known to exist [duplicate]

It is easily proved that prime gaps can be arbitrarily large by constructing the sequence of composites $(n+1)! + 2, (n+1)! + 3, \dots, (n+1)! + (n+1)$, which are divisible by $2, \dots, n+1$ ...
5
votes
3answers
96 views

Finding the possible Least Common Multiples of of numbers with Highest Common Factor 8

The Highest Common Factor of two numbers is 8. Which one of the following can never be their Least Common Multiple? The choices are as follow: A. 8 B. 12 C. 60 D. 72 The answer key states ...
2
votes
0answers
28 views

Asymptotics of $\sum_{\mathfrak{a}}\frac{n^{k-\epsilon}}{\mathfrak{N}\left(\mathfrak{a}\right)^{r\left(k-\epsilon\right)}}$

In this paper by Brian D. Sittinger, the following claim is made: For an algebraic number field $K$ with norm $\mathfrak{N}$, let $\epsilon=\left[K:\mathbb{Q}\right]^{-1}$. Then, taking the sum over ...
0
votes
2answers
30 views

all the squares in the multiplicative group $\mathbb{Z}_n^*$. [on hold]

I just want to know what this statement means: "all the squares in the multiplicative group $\mathbb{Z}_n^*$."
5
votes
2answers
53 views

Diophantine equation not solvable in $\mathbb{Q}$, but in $\mathcal{O}_p$

I'm trying to think of an example of a diophantine equation which can be solved in $ \mathcal{O}_p$ (meaning it can be solved $\mod p^k$ for all $ k $) for all prime $ p $'s, but not in $\mathbb{Q}$ ...
4
votes
1answer
45 views

Finitely Many Extensions of Fixed Degree of a Local Field

How does one show that there are only finitely many degree $n$ extensions of a local field? I understand how this follows from class field theory in the Abelian case but don't understand how to do the ...