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
3answers
23 views

Every integer greater than 1 is divisible by at least one prime. Can anyone please express this in logical notation

Every integer greater than 1 is divisible by at least one prime. Can anyone please express this in logical notation
0
votes
0answers
14 views

Stuck in quadratic forms and discriminats problem

So I'm stuck in a pretty easy question about discriminants and quadratic forms of equations. I have already proved one side of the problem: we suppose that $x_0, y_0$ are the solutions to the ...
0
votes
2answers
14 views

For $p>3$, prove that the primitive roots $\mod p$ occur in pairs, $u,v$, such that $uv$ is congruent to $1 \mod p$

I have never done a proof with primitive roots, so I'm not sure how to start this.
1
vote
0answers
26 views

How to convert a integral into the another?

There is a function here: http://functions.wolfram.com/NumberTheoryFunctions/PrimePi/21/01/01/0001/ How to convert it into the answer for indefinite integral $\int \pi(x) dx$ where pi(x) stand for ...
3
votes
2answers
42 views

integral roots for $f(x) = 41$ if $f(x) = 37$ has 5 distinct integral roots.

Given a polynomial $f(x)$ with integral coefficients and $f(x) = 37$ has 5 distinct integral roots, find the number of integral roots of $f(x) = 41$? My Approach: Say $f(x) = ...
0
votes
1answer
28 views

Prove that $a^4 \equiv 1 \bmod 5$ if $\space a \neq 5$

Prove that $a^4 \equiv 1 \bmod 5$ if$ \space a \neq 5$ I've tried showing this by induction. Clearly if $ a = 5$ then $ a \equiv 0 \bmod 5$ now if $a = 1$ then $a^4 - 1 = 0$ which is divisible by ...
5
votes
0answers
33 views

Given the factors of $N$, is there a method for computing the factors of $N-1$ or $N+1$?

Given the prime factorization of $N$, is there a known method for computing the prime factorization of $N-1$ or $N+1$, which is more efficient than the best known method for doing that without it? I ...
1
vote
1answer
17 views

count of Ordered Pairs such that their product is less than a number

I need a mathematical formulation for count of total ordered sets s.t. the product of two elements is less than an number, say n.. count{(i,j)}, s.t.i*j<=n
0
votes
3answers
54 views

If $d=\gcd(a+b,a^2+b^2)$, with $\gcd(a,b)=1$, then $d=1$ or $2$

Suppose $\gcd(a,b)=1$. Let $d=\gcd(a+b,a^2+b^2)$. I want to prove that $d$ equals $1$ or $2$. I get that $d\mid2ab$ but I can't find a linear combination that will give me some help to use the fact ...
0
votes
0answers
25 views

Is there any other integral of a special function that is undetermined?

Is there any other integral of a special function that is undetermined but yet the special function itself is continous? eg. the integral of the prime number counting function is undetermined By ...
1
vote
1answer
30 views

Comparing coefficients in finite field

We start with the wrong proof of the following theorem: $p| \binom{p}{k}$ for a prime $p$ and $0<k<p.$ Proof: $(1+x)^p \equiv 1+x \equiv 1+x^p \pmod{p}$ by Fermat's little theorem. Comparing ...
1
vote
1answer
27 views

Are we only knowing prime counting function's property but not its infinite expansion?

Are we only knowing prime counting function's asymptotic property but not its infinite expansion or even people could saying that there are no infinite series for the function? If yes, what are some ...
0
votes
2answers
12 views

Proof that in any base $b$, the result of multipling two numbers of $k$ digits, doesn't recuire more than $2k$ digits

The proof that I came up whit is: Let, $c$ be $b^0 r_0+ b^1 r_1+b^2 r_2+...+b^k r_k$ and $d = b^0 r_0'+ b^1 r_1'+b^2 r_2'+...+b^k r_k'$ then multipling both: $$(b^0 r_0+ b^1 r_1+b^2 r_2+...+b^k ...
2
votes
1answer
25 views

Calculate modulo of large numbers

I have $2^{2^n}+1$ and i want to calculate ($(2^{2^{^n}} +1 )\mod 19$). How can i do it if for example i choose $n = 19$. Can i use Fermat's Little Theorem?
2
votes
0answers
23 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then the equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers obviuosly, $ x^2-py^2 = -1 $ has no solution in integers. How to attack this problem? Thanks ...
0
votes
0answers
6 views

When does $f_{\omega+1}$ catch up the $G_n$-sequence?

Which is the minimal number k, so that $f_{\omega+1}(n) > G_n$ is true for all $n\ge k$ ? For the definition of $f_{\omega+1}$ look at wikipedia fast growing hierarchy $G_n$ is defined by ...
0
votes
0answers
28 views

No prime number divides one

I was reading Euclid's theorem and came accross this affirmation but no prime number divides 1 Is there any mathematical proof or is it an axiom of number theory ? Can this affirmation be ...
3
votes
3answers
75 views

How find this $x^3-5x+10=2^y$

let $x,y$ is positive integer,and such $$x^3-5x+10=2^y$$ find all $x,y$. since $$x=1\Longrightarrow 1^3-5+10=6$$ can't $$x=2,2^3-5\cdot 2+10=8=2^3$$ so $x=2,y=3$ $$x=3,LHS=27-15+10=22$$ ...
0
votes
0answers
13 views

How many omegas are there in $\large f_{\epsilon_0}$?

For a description look at fast growing hierarchy at wikipedia. $\large f_{\epsilon_0}$ is not defined any more, it is a power tower of omegas, but how many omegas ? I found a defition $$\large ...
0
votes
2answers
44 views

Find three numbers given their sum, product and sum of their squares

Given three unknown positive integers. Is it possible to find the three numbers if we are given their Sum->(a+b+c) = X Product-> (abc) = Y Sum of Squares-> (a^2 + b^2 + c^2) = Z
2
votes
1answer
55 views

Twin Prime conjecture current status

Can someone help me with a link to read about the status of the Twin Prime conjecture. I have browse on the internet and have read some articles but still I have no clue of the updated status of Twin ...
0
votes
2answers
26 views

Solving Linear Congruences $ax+c = b \pmod{m}$

I am facing this problem i know how to solve $ax = b \pmod{m}$. For example $16x = 52 \pmod{52}$: I know that the result is $0,13,26,39$ or $13k$ but what is the solution for $16x + 48 = 52 ...
5
votes
0answers
37 views

Problems that are made easy by using p-adic numbers

Does anybody know of elementary problems that can be be solved using the p-adics? Solutions are preferred.
0
votes
4answers
58 views

Prove that (integer + non-integer) never equals an integer.

My question is how do you prove that given an integer $x$ and a number $y$, the only way for $x + y$ to be an integer is if $y$ is also an integer. I can see how to prove by induction that an integer ...
10
votes
3answers
942 views

Is this already an equation/law that has been found?

So I was messing around with some numbers today and I have found a way to quickly add summations (probably not the first one to discover it but...) this only works when you start at 1 (i.e. ...
1
vote
1answer
40 views

Integer solutions of the equation $a^{n+1}-(a+1)^n = 2001 $

I am doing number theory and I came across that question $a^{n+1}-(a+1)^n = 2001 $. Find the integer solutions and show that they are the only solution. I really tried hard but i am nowhere near ...
5
votes
1answer
75 views

For $n\ge4$, prove that $1!+2!+\cdots+n!$ cannot be the square of a positive integer

I'm trying to prove this by induction but seem to be getting nowhere.
1
vote
3answers
88 views

how do i prove that $17^n-12^n-24^n+19^n \equiv 0 \pmod{35}$

How do i prove that 17n−12n−24n+19n≡0(mod35) for every possitive integer n. Can anyone give me a hint of how to start?
2
votes
0answers
35 views

Is there an infinite number of primes of the form (5^n)-2 and/or (5^n)+2?

I would like to know if there is a proof of this, that shows whether either one or both of the expressions: $5^n-2$ and $5^n+2$ will equal a prime number indefinitely. (Is the set of values for (n) ...
1
vote
1answer
27 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
-1
votes
3answers
98 views

An intutive way to think about odd and even numbers. [on hold]

What is an intuitive way to think about odd and even numbers? And about divisibility also...
1
vote
1answer
43 views

The difference set $D(\mathbb Z^*_n)$ of $\mathbb Z_n^*$

I wish to ask whether $D(\mathbb Z^*_n)=\mathbb Z_n^+$ given $n$ is odd. This is equivalent to proving that: For every $l\in\mathbb Z^+_n$, the set $l+\mathbb Z^*_n=\{a+l:a\in\mathbb ...
1
vote
1answer
36 views

Concerning squarefree numbers with 2 primes and squarefrees with 3 primes.

If a squarefree with two primes is a 2-prime and a squarefree with three primes is a 3-prime is there an integer N such that the number of 2-primes less than N is equal to the number of 3-primes less ...
3
votes
1answer
35 views

$4|(p-1) \implies$ there is an element $x$ of order $ 4$ modulo $p$.?

"$p \equiv 1 \mod 4 \implies 4 \mid (p-1) \implies$ there is an element $x$ of order $4$ modulo $p$." I am having a difficult time understanding why this implies there is an element $x$ of order $4$. ...
0
votes
0answers
8 views

Average Orders and Convolutions

If I know the average order of an arithmetic function $f=I*g$, where $I$ is the identity function defined by $I(n)=n$, is there a way to find the average order of $g$?
1
vote
0answers
58 views

Is there a power of 2 that, written backward, is a power of 5?

In this note the famous mathematical physicists Freeman Dyson gives an example of a true statement that is impossible to prove. Or so he states. The statement is as follow: Numbers that are exact ...
0
votes
3answers
22 views

RSA decryption problem

(e,n) = (17,323), with ciphertext 185 First compute $\phi(323) = \phi(17*19) = 16*18 = 288$ In order to find the decryption exponent, we must solve 17*d = 1 mod 288 This is equal to $d = ...
0
votes
2answers
18 views

How do I compute Euler phi function efficiently for repeated prime factors?

In RSA decryption problems, you have to compute $\phi(n)$ and then sometimes $\phi(\phi(n))$ quickly. For example, I had to compute $\phi(2^5)$ for one particular problem and it seems to me (for ...
2
votes
0answers
23 views

Does Shor's algorithm work for noncommutitive or nonassociative algebras?

Shor's algorithm is said to solve the hidden subgroup problem for finite Abelian groups, at least according to the Wikipedia article I read. This means that it can be used to solve factoring or ...
1
vote
1answer
18 views

Greatest common divisor and exponent relationship

For a > 1 show that the gcd$(a^n - 1, a^m - 1) = a^{(m,n)} - 1$ What are some useful equalities that might help in proving this relationship? I believe the constrains for $m,n$ are all positive ...
4
votes
3answers
72 views

Show that there is no integer n with $\phi(n)$ = 14

I did the following proof and I was wondering if its valid. It feels wrong because I didn't actually test the case when purportedly n is not prime, but please feel free to correct me. Assume there ...
2
votes
4answers
68 views

Find a value of $n$ that has exactly 32 divisors

I know that I could simply multiply the first $32$ primes together but is there some other way to ascertain the answer to this number theory problem?
1
vote
0answers
60 views

Is my conjecture correct? Any advice on how to solve this conjecture?

I was doing problem 6.3 from here. To make this less programming and more math oriented: GCDMany is equivalent to using Euclid's method (using mods and NOT ...
1
vote
0answers
25 views

Open Ball under the p-adic Norm

I'm trying to figure how, if it's even possible, to draw an open ball using the p-adic norm. My definition of the p-adic norm I'm using is: $ \lvert x \rvert_p $ = $p^{-ord_px}$ if $x \neq 0$ and ...
2
votes
0answers
22 views

Is factoring in other quadratic rings harder than factoring integers?

I've been wondering if factoring in quadratic rings that are unique factorization domains (principle ideal domains?) is more difficult than factoring integers. Today we can apply the general number ...
0
votes
0answers
7 views

Particular type of input to gather information on certain types of encryption schemes

Consider a simple case in which information is sent is considered as it's binary equivalent and then those numbers are considered as base 10 and used as inputs to an equation over a number field of ...
1
vote
1answer
39 views

$ax^2 + b$ and infinitely many primes: Does existence proof exist?

The question is on a subset of Bunyakovsky's Conjecture on an infinite number of primes existing in integer polynomials of degree higher than $1$. The conjecture itself is open. I have not been able ...
7
votes
1answer
83 views

GCD of $a^n + b^n$ and $c^n + d^n$

Prove or disprove that there does not exists any integers $a,b,c,d > 1$ such that $a,b,c,d$ are pairwise coprime, and $a^n + b^n$ and $c^n + d^n$ are also coprime for all integer $n > 1$. I ...
5
votes
1answer
187 views

Exponentials of rational numbers

Does there exist an $$0<x<1$$ such that $$\forall q \in \mathbb{Q^+}$$ $$q^x \in \mathbb{Q^+}$$
0
votes
2answers
28 views

The sum of two triangular numbers.

When triangular number is the square of an elementary formula is obtained. Sam got a couple of pieces, but I wonder how the formula looks opisyvayushaya sum of two triangular numbers is the square of ...