Exercises
Multiple Choice
Articles
Open Problems
Login
19 items
Topic:
Number Theory
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Undergraduate
By
Shiva Kintali
on Sept. 28, 2013 | Updated Jan. 4, 2018
Primes and divisibility
Prove the following without using Fermat's little theorem or Euler's totient theorem. Here \(a\ |\ b\) means \(a\) divides \(b\). Prove that for every prime number \(p\) and every pair of integer…
Mathematics
Number Theory
divisibility
primes
0
Undergraduate
By
True Putnam
on June 7, 2012 | Updated Jan. 4, 2018
Putnam 2005 A1
Prove that every positive integer can be expressed as a sum of numbers of the kind \(2^i3^j\), where no term in the summation divides the other. For example : 1) 14 = 8 + 6 is a valid represent…
Computer Science
Mathematics
Algorithms
Number Theory
dynamic programming
0
High School
By
Shiva Kintali
on June 2, 2013 | Updated Dec. 6, 2017
Prime magic
Let \(p\) be a prime number bigger than 3. Prove that \(p^2-1\) is always divisible by \(24\).
Mathematics
Number Theory
primes
0
Undergraduate
By
Shiva Kintali
on Oct. 12, 2013 | Updated Jan. 4, 2018
Ramsey primes
For every integer \(m \geq 1\), there exists an integer \(p_0\) such that, for all primes \(p \geq p_0\), the congruence \(x^m + y^m \equiv z^m (\mbox{mod}\ p)\) has a solution with positive …
Mathematics
Number Theory
primes
ramsey theory
0
High School
By
Shiva Kintali
on Dec. 14, 2013 | Updated Jan. 4, 2018
Legendre's Theorem
Prove the following Legendre's Theorem : Legendre's Theorem : The number \(n!\) contains the prime factor \(p\) exactly \(\sum_{k \geq 1}{\lfloor \frac{n}{p^k} \rfloor}\) times.
Mathematics
Number Theory
primes
0
Graduate
By
Shiva Kintali
on June 12, 2012 | Updated Dec. 6, 2017
Solving Discrete-logarithm
Consider the following problem : Given a \(y\) such that \(0 < y < p\), where \(p\) is a prime number, find an \(x\) (if it exists) such that \(2^x ≡ y\ \mbox{mod}\ p\). Let \(n\) be the number …
Computer Science
Mathematics
Algorithms
Number Theory
primes
0
Graduate
By
Shiva Kintali
on June 19, 2012 | Updated Dec. 6, 2017
Primality is in NP $\cap$ co-NP
Primality is the following problem : Given a positive integer \(n\), is \(n\) prime ? Note that the size of the input is the number of bits used to represent \(n\). Easy : Show that Primality…
Computer Science
Mathematics
Complexity Theory
Number Theory
primes
0
Graduate
By
Shiva Kintali
on Aug. 13, 2012 | Updated Dec. 6, 2017
Integer Factoring is in NP $\cap$ co-NP
Formulate an appropriate decision version of Integer Factorization and prove that it is in NP \(\cap\) co-NP. There are two ways of proving this : (Easy) Use the fact that Primality is in P. Witho…
Computer Science
Mathematics
Complexity Theory
Number Theory
factoring
NP completeness
0
Undergraduate
By
Shiva Kintali
on Dec. 14, 2013 | Updated Jan. 4, 2018
Product of Primes
Prove that \(\displaystyle \prod_{p \leq x} p \leq 4^{x-1}\) for all real \(x \geq 2\). Here the product is taken over all prime numbers \(p \leq x\).
Mathematics
Number Theory
primes
0
High School
By
Shiva Kintali
on Dec. 31, 2013 | Updated Dec. 6, 2017
Prime gaps are not bounded
Prove that the gap between consecutive primes is not bounded, by proving the following theorem. Given any integer \(k \geq 1\), there is a number \(N\) such that \(N+1, N+2, N+3, \dots, N+k\) are …
Mathematics
Number Theory
primes
1
2
next page »
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
linear equations
primes
counting
conditional probability
interview question
vertex cover
math puzzle
expectation
basics
fibonacci
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×