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)

0
votes
1answer
23 views

Determine running time of recurrence relations using a QUICK/easy method!

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
0
votes
2answers
24 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
1
vote
3answers
50 views

Finding all the values of n, such that $ \varphi (n) = 12 $ [duplicate]

I have not broken this down very far. I have come to the conclusion that there are infinitely many values for n where there exists 12 coprimes to n. Since there are infinitely many primes, and primes ...
0
votes
2answers
14 views

A problem regarding Extended Euclidean Algorithm

A Linear Diophantine Equation is of the following form: Ax+By+C=0, where,gcd(A,B)=d and A=da,B=db.If (x1,y1) is a solution of the diophantine equation, every solution is of the form: x=x1+bt,y=y1−at ...
2
votes
0answers
42 views

What is known about$\sum\limits_{p\text{ prime}} \frac{1}{p^2-1}$?

Are there some known results for $\sum\limits_{p\text{ prime}} \dfrac{1}{p^2-1}$? I wasn't able to find anything about this sum in the internet or in my books!
0
votes
1answer
6 views

Solving a Extended Euclidean Algorithm related problem

Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types: Type 1: each box costs c1 Taka and can hold exactly n1 marbles Type ...
1
vote
2answers
18 views

Whether an equation has a solution

Will the following equation have a solution in $\mathbb Z$? $n_1^2+n_2^2+n_1n_2=3$ for $n_1\neq n_2$
5
votes
2answers
53 views

Determinant value of $2 \times 2$ matrices

Let $a,b,c,d$ be integers such that $\dfrac ac \in \mathbb Q^+$\ $\mathbb Z^+ $ and $\dfrac bd \in \mathbb Q^- $ \ $ \mathbb Z^-$ ; then how many solutions does $|ad-bc|=1$ have ?
0
votes
0answers
11 views

How can we solve the module function related equation?

Suppose that $\alpha,\beta=1,2,\cdots,n_1n_2$, and they satisfy the equation $$ \beta-\textbf{mod}(\beta,n_2)=\alpha-\textbf{mod}(\alpha,n_2) $$ where $\textbf{mod(,)}$ is the module function as usual ...
0
votes
0answers
28 views

Can Legendre's theorem really help solve this equation: $ax^2+by^2=cz^2$?

let $a,b,c,x,y$ be non-zero positive integers such that $$\gcd(x,y,z)=1$$ $$ \gcd(x,a)>1$$$$ \gcd(y,b)>1$$ $$ \gcd(z,c)>1 $$ If $a,b,c$ are square-free, find all the non-trivial integral ...
1
vote
2answers
29 views

For any integer a, if $6|(3−a)$, then $3| (a−2)$.

Prove: For any integer a, if $6|(3−a)$, then $3| (a−2)$. I've been trying to work this problem for a while, but missed a day of class and can't seem to work it out.
3
votes
0answers
23 views

How many zeros within a number

Let noughts(n) be the number of noughts needed to write n in base 10.If n is given how can I find out the value of noughts(n) . I myself have tried to compute noughts(n) by examining all the digits ...
-1
votes
4answers
75 views

Solve this number theory problem

Why is a number written in decimal evenly divisible by 9 if and only if the sum of its digits is a multiple of 9?
7
votes
2answers
226 views

Proving a palindromic integer with an even number of digits is divisible by 11

I'm in an introductory course for discrete math so I'm a novice at English proofs. I'm not sure if my reasoning here is valid or if I'm using modular arithmetic correctly. Specifically the line I ...
0
votes
0answers
22 views

Remarks on a Previous Post

Recently I have been reading this post and I have noted something significant in the fake argument. As one can easily see that the basic idea behind the argument had been to show that the sequence ...
-1
votes
3answers
49 views

Prove there do not exist natural numbers m and n such that $7m^2 = n^2$.

Prove there do not exist natural numbers $m$ and $n$ such that $7m^2 = n^2$. Proof: Using the Fundamental Theorem of Arithmetic, we can write $m=(p_1^{r_1 }\ldots p_n^{r_n})$ and $n=(q_1^{s_1 }\ldots ...
0
votes
0answers
19 views

$n_p$ - the largest power of the prime $p$ which divides $n$

I was reading this article called "On A Theorem of Frobenius: Solutions to $x^n=1$ in Finite Groups" by I.M. Isaacs and G.R. Robinson (www.jstor.org/stable/2324902). In the third para of the first ...
0
votes
1answer
25 views

Numbers of the form $n^k-1$

I know that numbers of the form $2^k-1$ are called Mersenne numbers. But are there other special numbers which are one less than a power of an integer (for instance, does $3^k-1$ have some special ...
3
votes
1answer
45 views

Fermat's Little Theorem: group and multiplication modulo

$p$ is a prime number. $G$ is a group of integers $\{1,2,\dots,p-1\}$ under multiplication mod $p$. $d$ is a divisor of $(p-1)$ Is it possible to prove that the number of elements $a$ in $G$ such ...
0
votes
1answer
12 views

Gaussian sums values

I have the following problem: Denoting $S(q,a,\chi ) = \sum_{x=1}^q \chi (x) e(ax/q)$, where $\chi $ is an arbitrary character modulo $q$, I have to prove $$\sum_{a=1}^q \vert S(q,a,\chi ) \vert ^2 = ...
0
votes
1answer
24 views

How many ordered bases can be found for $\mathbb{Z}_p^n$ over filed $\mathbb{Z}_p$?

Take $\mathbb{Z}_p^n$ as a linear space over $\mathbb{Z}_p$. Now you can imagine multy bases for this space. (please leave a comment or have an edit if question is not clear enough.)
1
vote
1answer
13 views

reducing the modulus of a Dirichlet character

Let $\chi$ be a Dirichlet character modulo $N$. Let $M$ be a positive divisor of $N$ such that $$\text{radical}(N)=\text{radical}(M).$$ Is $\chi$ be a character modulo $M$? Best regards.
0
votes
1answer
24 views

Modular arithmetic - is this a “legal” substitution?

I know that $$a \equiv b ~(\text{mod}~3)$$ and $$c \cdot a \equiv 1 ~(\text{mod}~3)$$ Can I substitute $a$ with $b$? I mean: $$c\cdot b \equiv 1 ~(\text{mod}~3)$$
2
votes
1answer
19 views

Dirichlet character modulo p

How can I prove that if $\chi$ is a non-principal character modulo $p$ prime, then $\chi (-1) = \overline{\chi} (-1)= \pm 1$ and $\sum_{x=1}^p \chi (x) e^{2\pi i x}=0$? For the first question, I just ...
1
vote
0answers
12 views

no quotient of $\mathcal{O}_{\mathbb{C}_K}$ modulo a proper ideal containing $p$ is a perfect $\mathbb{F}_p$-algebra?

I am reading the Notes on $p$-adic Hodge theory of O. Brinon & B. Conrad . Can someone explains the following things to me? «... no quotient of $\mathcal{O}_{\mathbb{C}_K}$ modulo a proper ideal ...
1
vote
0answers
68 views

Cardinality of a set of polynomials where the sum of the cubes of the roots is zero

Let $C\subseteq \mathbb Z\times \mathbb Z$ be the set of integer pairs $(a,b)$ for which the 3 complex roots $r_1,r_2,r_3$ of the polynomial $p(x)=x^3-2x^2+ax+b$ satisfy $r_1^3+r_2^3+r_3^3=0$ .Then ...
3
votes
1answer
35 views

$t^{\frac{1}{t-1}}$ and $t^{\frac{t}{t-1}}$ need to be integers

$t^{\frac{1}{t-1}}$ and $t^{\frac{t}{t-1}}$ need to be integers. Is this only for $t = 2$ and $t = \frac{1}{2}$ true? $t$ can be any positive real number Could anyone give me a hint how to prove it, ...
1
vote
2answers
63 views

Prove that there exist a prime having last $65050$ digits the largest known prime

The largest known prime is of the $65050$ digits. Prove that there exist another prime which ends in the same $65050$ digits of largest known prime.
1
vote
1answer
18 views

if $p=(a+ib)(c+id)$ and $p^2 = a^2 + b^2$ then $p\mid a$ & $p\mid b$

We're working on Gauss integers... p is an odd prime such that $p \not\equiv 1 \pmod 4$. We want to prove that if there is $(a,b,c,d) \in \mathbb{Z}^4$ such that $$p = (a+ib)(c+id) \text{ ...
2
votes
0answers
39 views

Pell's Equation and the Pigeon Hole Principle

David Speyer gave a beautiful application of the pigeon hole principle here to show that Pell's equation $$x^2-Dy^2=1$$ has infinitely many integral solutions. I was wondering if anybody knows the ...
0
votes
0answers
8 views

Twisted logarithm power series

I recently encountered a power series similar to the one of the $\log(1-x)$ of the form $$ F(x)= \sum_{n=1}^\infty \frac{\psi(n)x^n}{n}, $$ where $\psi$ is some Dirichlet character. Has anyone here ...
2
votes
1answer
34 views

Average order of Eulers totient function squared

I was wondering if one has a nice asymptotic formula for the sum $$\sum_{n\le x} \phi(n)^2$$ and if so, how does one calculate it. I know that one has $\sum_{n\le x} \phi(n) = ...
0
votes
1answer
33 views

Is $r_2$ a uniformly at random value in $Z_n$, where $r_2=r_1 . m$

Let $m$ be an arbitrary value in $Z_n$, where n is RSA modulo (n=p.q, where p and q are large primes). Then have: $r_2=r_1 . m$, where $r_1$ is a value chosen uniformly at random : $r_1\in Z^*_n$. ...
1
vote
0answers
28 views

Concise Number Theory Book [duplicate]

I'm having problems relating different formulas etc with each other in number theory. So I need recommendations for a really good book on introduction to number theory which is precise and has plenty ...
2
votes
1answer
73 views

Number theory / Group theory: consecutive integers divisible by at least n prime numbers

Claim: There exist 15,251 successive positive integers $a_1, a_2\dots,a_{15251}$ such that each $a_i$ where ($1\le i\le 15251$) is divisible by at least 251 different prime numbers Is there a neat ...
0
votes
1answer
24 views

Prove that for a sequence of people sets $S_1,…,S_d$, $\Delta_i \not = 0$ for all people

We have $k$ people $p_1,...,p_k$, and $d$ people sets $S_1,...,S_d$, where the sizes of $S_1,...,S_d$ can vary between $1$ and $k$ (so each $S_1,...,S_d$ is a set of some people from ...
4
votes
1answer
66 views

Proof of $p_n<n^2$ by Elementary Means

Is there any proof of the inequality $p_n<n^2$ (for all sufficiently large $n$) by elementary means and without using Prime Number Theorem? I searched in google but in vain. The results that I ...
4
votes
0answers
29 views

Arithmetic Functions: Evaluate $ \sigma(210)$ and $d(63)$

Evaluate $ \sigma(210)$ and $d(63)$ I'm not sure if I got this correct, so here is my attempt. By Theorem 6.3, suppose we have $n=p_1^{\alpha 1}...p_s^{\alpha s}$, then $d(n) =(\alpha_1 ...
0
votes
0answers
26 views

A Contradiction of Riemann Zeta Residues

We can show (1+2+3...+n)^2 = 1^3 + 2^3 + ... +n^3, which holds for any finite n, shouldn't this imply Z(-1)^2 = Z(-3)? However, this does not hold if we look at the residues of the zeta function ...
0
votes
1answer
18 views

Finding permutation $a$ given $b$ and conjugate $a^b$

Normally we define a conjugate relationship as $$a^b = b~a~b^{-1}$$ But I don't know how to find $a$ given that we know $b$ and $a^b$.
3
votes
1answer
40 views

Eulers totient function divided by $n$, counting numbers in the set [1,m] that are coprime to n

If we divide Euler's totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is ...
1
vote
0answers
42 views

Show that $-1$ is a square $\mod n$, if $n\equiv 1\mod 4$?

I am trying to prove that $-1$ is a square modulo $n$ if, and only if $n\equiv 1\mod 4$. One direction i think i have done... So, we have that $n\equiv 1\mod 4$, from this follows that $n$ must be ...
0
votes
1answer
21 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...
2
votes
0answers
28 views

A primitive root exists modulo $n$ if and only if $n=2$, $n=4$, $n=p^k$, or $n=2p^k$ with $p$ an odd prime.

I have already proven that primitive roots exist modulo $p^k$ and $2p^k$ for an odd prime $p$. I'm having trouble proving the other direction. Is it simply due to the fact that if $p,q$ are distinct ...
0
votes
2answers
20 views

How to find sum of powers from 1 to r

Let say I have two numbers n power r. How can we find sums of all powers. For example if n = 3 and r 3 then we can calculate manually like this ...
0
votes
1answer
29 views

Arithemetic series addition

Lets say I have M= 1+2+3+4+5+6+7.... (to infinity) and I have another sequence,N= 6+14+22+30..... (to infinity) is it possible to say that N = 4M +2 ? Or is there another way that I can write ...
0
votes
0answers
14 views

galois group of a biquadratic involving primes.

Let $f(x)=x^4-px^2+q \in \mathbb Q[x]$ be a polynomial with $p,q$ be distinct primes. Prove that $f$ it's irreducible over $\mathbb Q$. Prove that it's Galois group is the dihedral. I proved the ...
0
votes
1answer
18 views

Partial sums of powers of the divisor function

It is easy to establish that $$\sum_{n\le x}\tau(n) \sim n\log n$$ How would one find good bounds on $$\sum_{n\le x} \tau(n)^k $$ for some $k > 0$
1
vote
2answers
16 views

If p is an odd prme and (t,p) = 1, then t^2 is not a primitive root (modp).

If p is an odd prime and (t,p) = 1, then t^2 is not a primitive root (modp). proof: If g is a primitive root (modp) and if t is an integer such that (t,p) = 1, then there exist an integer k such ...
1
vote
0answers
34 views

A probabilty of error calculation

Let's assume I have $N$ binary strings $\{T_1,T_2,\ldots,T_N\}$ of length $L$. All these strings satisfy a minimum hamming distance with respect to a reference binary string R with $\|R\|_1$ ones and ...