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

Combinations of sets raised to the power of a prime modulus

This is a problem out of the text Introduction to the Theory of Numbers by Niven, Zuckerman, and Montogmery and I am having quite a bit of trouble with it. I tried to prove it directly, but that ...
1
vote
0answers
20 views

On the partial zeta function

Let $F$ be a number field and $S$ be a finite set of places of $F$ including archimedian places. Let $\zeta^S(s)$ be the partial L-function, that is the meromorphic continuation of the product of ...
2
votes
2answers
78 views

Can Andrica's conjecture be proven by proving a tighter upper bound for prime gaps?

I checked some differences between square roots of various natural numbers and I am wondering what is required to prove Andrica's conjecture. Would a tighter upper bound for the prime gap above $n$ be ...
6
votes
0answers
86 views

Proving that $\left|\Re\left( \frac{1+i\sqrt{7}}{2}\right)^n\right| \to \infty$ [duplicate]

Let $u_n=\displaystyle\Re\left( \frac{1+i\sqrt{7}}{2}\right)^n$ Prove that $|u_n| \to \infty$ This appeared in a recent issue of French Revue de la Filière Mathématiques, as it was ...
0
votes
0answers
22 views

Is there a discrete relationship shared between patterns and series or sequences?

Maybe to clarify a little, I feel that patterns are related to sequences and series, in that a series or sequence can define a pattern. However I have yet to find any reference to such being the case ...
-1
votes
0answers
35 views

How do you make the lighest change possible?

Suppose you have coin denominations $1 = c_1 < c_2 <... < c_k$ each with associated weight $w_1, ..., w_k$ and that you are trying to make change for $n$ cents. How can you make the ...
1
vote
1answer
45 views

Remainder of a summation divided by $2^{12}$

For a positive integer $n$, let $f(n)$ be equal to $n$ if there is an integer $x$ such that $x^2-n$ is divisible by $2^{12}$, and let $f(n)$ be $0$ otherwise. Determine the remainder when ...
1
vote
1answer
17 views

$\binom{p^{\alpha}-1}{k} = (-1)^k\pmod{p}$? [duplicate]

I need to show that $$\binom{p^{\alpha}-1}{k} = (-1)^k\pmod{p}$$ for $0 \leq k \leq p^{\alpha}-1$. Not really sure how to start going about this... how should I transform the term on the left? ...
1
vote
1answer
30 views

Five digit numbers where each digit can appear up to three times

The question is to determine how many five-digit numbers there are (using the digits 0-9) where each digit can appear up to three times in the number. The total number of numbers that can be made ...
3
votes
1answer
27 views

Toy cryptographic hash function for education purposes?

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for ...
1
vote
0answers
73 views

Longest sequence of distinct squares which sum to a given number

I want to find the longest sequence of distinct integer squares $1 \le a_1^2 < a_2^2 < \dotsb < a_k^2$ such that $$a_1^2 + \dotsb + a_k^2 = n$$ where $n$ is a given [positive] integer. In ...
0
votes
1answer
37 views

Prove that 12 has no primitive root

So I've got to prove that there exists no integer $a$ such that $a$ has order 4 mod 12. How can I do this? EDIT: Can I just try every integer less 12 and co-prime to 12 i.e. 5,7,11 Why does it ...
2
votes
2answers
52 views

How to prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?

How can i prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?
0
votes
1answer
18 views

Question about Linear Diophantine Equation.

A Linear Diophantine Equation is of the following form: $Ax+By+C=0$, where $\gcd(A,B)=d$ and $A=da,B=db$. If $(x_1,y_1)$ and $(x_2,y_2)$ are two solutions of the equation, then $b \textrm{ $|$ } ...
3
votes
0answers
49 views

Are there any positive integers $a, b, c, d$ such that both $(a, b, c)$ and $(b, c, d)$ are Pythagorean triples?

Pythagorean triple is a triple of integers $(a, b, c)$ such that $a^2+b^2=c^2$. Is there any Pythagorean triple such that, not only $a^2+b^2$, but also $b^2+c^2$ is a square number? If not, how to ...
3
votes
0answers
72 views

Sum of roots (number theory)

Let k,m∈ℕ. Let a1,a2,...,ak>0 and b1,b2,...,bm>0. Let for all natural n, n>1 Prove that k=m. Prove that a1a2...ak=b1b2...bk Prove that if each of the two sets of numbers sort of growth, then ...
1
vote
4answers
57 views

$z^2=x^2+y^2$ Prove that $4\mid xyz$ ($xyz$ is divided by $4$)

$z^2=x^2+y^2$ where $x,\ y,\ z$ - integers Prove that $4\mid xyz$ ($xyz$ is divided by $4$) All possible rest in divided by $4$ in this case is $1$. That's all I noticed.
1
vote
1answer
54 views

Find all positive integer that $2^{2^n}+5 $ is a prime number. [duplicate]

Find all nonnegative integer that $2^{2^n}+5 $ is a prime number. For $n=0$ we have $7$ - correct For $n=1$ we have 9 - false For $n=2$ we have 21 - false For $n=3$ we have 259 ... Maybe any ideas ...
3
votes
0answers
31 views

Decide if radical expression equals a given rational number

Given a radical expression an a rational number. Is there an algorithm to decide if the expression equals the number? Example: $(\sqrt{\sqrt[5]{74} - \sqrt[14]{78}})^{356}+\sqrt[6]{63} \overset{?}= ...
3
votes
3answers
53 views

Finding all solutions for to the equation $x^3 = 0\ {\rm mod}\ 9$

How do I go about finding the solutions to: $$ x^3 = 0\mod 9 $$ Any help is greatly appreciated thank you
0
votes
1answer
18 views

A extended euclid algorithm related problem

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 ...
4
votes
1answer
45 views

Factorial equation

I'm trying to find all nonnegative integer solutions to $x!^2=z!$. Intuitively, I think the solutions are the trivial ones with $x=0,1$ and $z=0,1$. I'm not sure how to show that there is no more ...
0
votes
1answer
30 views

Prove for all $x \in \mathbb{R}$, there is some $y \in [0,1)$ such that $x \equiv y \mod \mathbb{Z}$

So my logic is as such choose any $x$ say $99.05$. Then I can find $y \in [0,1)$ such that $99.05-y \in \mathbb{Z}$ doesn't $y$ have to be $0.05$? Congruences are a little more difficult when you let ...
0
votes
1answer
32 views

Diophantus problem

I was given following problem as an example of early mathematics with the solutions. But it seems i can't understand from where they are getting the 35z^2 = 5 from in the solutions. Could someone ...
1
vote
0answers
30 views

The Existence of “Simple” Prime Generating Functions

Obviously, we do not know an explicit and easily manipulable formula for finding every prime - that is, a function $f(n)$ which yields the $n^{th}$ prime. I've seen plenty of formulas that "cheat" in ...
0
votes
2answers
26 views

How can I use the congruence property to determine GCD?

As per my text, the congruence property is: If a > 0, b, and b' are integers such that $$b \equiv b' (mod\ a)$$ then $$(a,b) = (a,b')$$ I'm trying to use that to determine (7,150) and (28,-288). Any ...
0
votes
1answer
34 views

Can we use the natural logarithm to find a previous prime?

Using any natural number $n \geq 3$ , can we set up a formula with the natural logarithm of something $x$ to find a previous prime? My calculations tell me strongly that the answer is yes, but I have ...
8
votes
1answer
164 views

Cube roots of five

This is not really homework. I might be able to do this myself in time, from the methods in Ireland and Rosen. Note that every number has exactly one cube root $\pmod q$ for any prime $q \equiv 2 ...
3
votes
1answer
39 views

Show $\sum\limits_{b=0}^{p-1}\left(\frac{b}{p}\right) = 0$

Show $\sum\limits_{b=0}^{p-1}\left(\frac{b}{p}\right) = 0$ The resources I have consulted said to use the fact that the number of quadratic residues $\text{mod } p$ is $\frac{p-1}{2}$ but I have no ...
0
votes
2answers
22 views

Decimals and Rational numbers

How do you prove: Q1) Why is every rational number (say m/n, where m and n are both positive integers) either a terminating or a repeating decimal? Q2) Why is every repeating decimal (or terminating ...
-2
votes
1answer
50 views

Find minimum possible area of brush

A rectangular brush has been moved right and down on the painting. Consider the painting as a $n × m$ rectangular grid. At the beginning an $x × y$ rectangular brush is placed somewhere in the frame, ...
2
votes
1answer
46 views

smallest element order $p$ in $\mathbb Z^*_{p^2}$

I would like to write an efficient algorithm to find the smallest element of order $p$ in $\mathbb Z^*_{p^2}$, where $p$ is a prime number. Therefore I calculate $a^{p-1} \pmod{p^2}$ for every ...
0
votes
2answers
53 views

Solving a Linear Diophantine Equation

A Linear Diophantine Equation is of the following form: $Ax+By+C=0$, where $x_1 \leq x \leq x_2$ and $y_1 \leq y ...
0
votes
2answers
20 views

Summing powers of complex root of unities gives 0

I have a question regarding a proof. Let $z_N$ denote the complex N'th root of unity, from which we have the identities $(z_N)^n=1$ $\sum_{i=0}^{N-1}{(z_N)^i}=0$ Now let $N=r\cdot t$ and let ...
0
votes
0answers
7 views

What is the relation between the upper bound,low bound of simple continued fraction expansion of quadratic algebraic numbers and the integer

What is the relation between the upper bound,low bound of simple continued fraction expansion of quadratic algebraic numbers and the integer As we know,$\sqrt{14}= [3;1,2,1,6,1,2,1,6…]$,let $B_u,B_l$ ...
5
votes
1answer
72 views

When is the next palindrome?

Okay, this is more just for fun than anything else. I'm driving in my car today, (true story) and my odometer is about to hit $81,818$. So, being a math nerd and all, I immediately see the pattern ...
1
vote
0answers
10 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
3
votes
1answer
44 views

Some questions on the formation of the BSD conjecture

I'm quite curious how Birch and Swinnerton-Dyer formed their famous conjecture in the beginning of 1960s. I read some paper of Birch and Swinnerton-Dyer, as well as some paper of Tate and several ...
4
votes
1answer
98 views

Existence of $\{a_{n}\} $ and $\{b_{n}\}$ such that $a_{n}(a_{n}+1)|(b^2_{n}+1)$

Show that: there exist two sequences $\{a_{n}\}$ and $\{b_{n}\}$ that are monotonically increasing (or $a_{n+1}>a_{n},b_{n+1}>b_{n},\forall n\in N^{+}$) and for any positive integer $n$ ...
1
vote
2answers
39 views

A stricter Fermat's little theorem

By Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod{p}$ for all primes p. But it is often possible to find $x$ such that $a^{x} \equiv 1 \pmod{p}$ and x < p - 1. Is there anyway to ...
0
votes
1answer
51 views

Can we not apply the Hensel Lifting Lemma in this case?

Check if the equation $x^2=-1 \text{ in } \mathbb{Z}_2$ has a solution, and if it has, calculate the three first positions of the solution. So, we are looking for a solution $\pmod 2$, one solution ...
0
votes
1answer
42 views

PNT and Maximal Prime Gap Connection? [closed]

Are the formulas for estimating maximal prime gaps related to the Prime Number Theorem? Why do they both use the natural logarithm? Is the formula in the conjecture that there is always a prime ...
0
votes
2answers
70 views

Prove that if $p$ is a prime and $k$ is an integer, there are two integers $x$ and $y$ that satisfy $x^{2} + y^{2} + k \equiv p$ [closed]

Prove that if $p$ is a prime and $k$ is an integer, there are two integers $x$ and $y$ that satisfy $$ x^2 + y^2 + k \equiv 0 \pmod p. $$
0
votes
1answer
80 views

Distance between powers of 2 and 3

As we know $3^1-2^1 = 1$ and of course $3^2-2^3 = 1$. The question is that whether set $$ \{\ (m,n)\in \mathbb{N}\quad |\quad |3^m-2^n| = 1 \} $$ is finite or infinite.
2
votes
2answers
59 views

Chinese Remainder Theorem RSA

I want to solve the following modular quadratic equation: $x^2 \equiv 188 \pmod {437}$ using the fact that $437$ can be factorized by the primes as: $19⋅23$. So far I have done: $$x^2 \equiv 188 ...
3
votes
2answers
110 views

The Conjecture That There Is Always a Prime Between $n$ and $n+C\log^2n$

Let $n$ be 113. Use $n+C\log^2n$ to find the next consecutive prime or at least approximately how far away it is. Will you show me how to work this out step by step to show me how to use this formula? ...
1
vote
3answers
55 views

Finding if a number is prime by looking at the sum of their digits

Take a number $N = \overline{abcdef...}$ where $a, b, c, d,e,\dots$ are the digits of $N$. Let $k$ be the sum of those digits : $a+b+c+d+e+... = k$ If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ ...
2
votes
1answer
54 views

When is “being a linear algebraic $k$-group” preserved?

Let $G$ be a linear algebraic group over a field $k$, with Char$(k)=0$. What "group-theoretical operations" preserve the property of "being a $k$-linear algebraic group"? For example When ...
3
votes
1answer
53 views

Number of answers of equation amongs odd natural numbers

How many answer The following Equation has, in set of odd natural numbers? $x_1+x_2+...+x_k=n$, $k \equiv^2 n$ Solution: Comb ( [(n+k)/2]-1, k-1), comb means combination. how we get this?
1
vote
2answers
46 views