Ask Dr. Math

College Archive

Browse College Number Theory
Stars indicate particularly interesting answers or good places to begin browsing.

Selected answers to common questions:
    Testing for primality.

---

Partitions and Products [01/02/2003]

What is the best way of dividing an integer into parts so that the product of the parts will be as large as possible? Is there a universal law that tells us what partition will produce the maximum product for any given number? And can such a law be proved?

Patterns in Repeating Decimals [08/06/2003]

Why do certain number sequences repeat in the decimal expansions of common fractions?

Pell-like Diophantine Equations [10/05/2010]

How do you solve exponential Diophantine equations in two variables? Even after seeing recurrence relations and modular arithmetic simplify his original problem, a student remains curious about additional strategies, so Doctor Vogler obliges by outlining more advanced methods.

Perfect Numbers [06/15/2002]

Please show that any even perfect number ends in 6 or 8.

Perfect Square [10/26/2001]

If a and b are positive integers such that (1+ab) divides (a^2+b^2), show that the integer (a^2+b^2)/(1+ab) must be a perfect square.

Pigeonholes and Remainders [12/27/2003]

How can I show that in any collection of 52 distinct positive integers, there will be two distinct numbers whose sum or difference will be divisible by 100?

Polya-Burnside Lemma [07/02/1999]

Given unlimited amounts of 2 types of beads, how many unique necklaces can you make using exactly k beads?

Polynomial Divisible by 7 [11/14/2001]

Prove that 2^(3n+1) + 4^(3n+1) + 1 is divisible by 7.

Powers of 2 Proof [03/24/2003]

Prove that any number that is not a power of 2 can be expressed as a sum of two or more consecutive positive integers, but that this is not possible for powers of 2.

Predicting Number of Decimal Digits in a Binary Number [03/10/2004]

I am trying to write a function that will return the number of decimal digits from a binary number without actually converting from binary to decimal. Is there a way to determine which length is correct without going through a complete conversion?

Primality Testing [12/02/2004]

How can I determine if a given number is prime?

Prime Factors, Modular Arithmetic, and Using Pari [08/08/2007]

Suppose we have two positive integers 'a' and 'b'. Is there a method to find a positive integer 'k', such that a + bk = x^2 for some integer 'x'? In other words, how can we find a positive integer 'k', such that 'a + bk' is a square?

Prime Numbers between N and 1+N! [04/25/2003]

Prove that for each natural number N, there exists a prime number Q such that N is less than or equal to Q and Q is less than or equal to 1 + N!

Prime Numbers Proof [05/23/2005]

Prove that every prime number is the leg of exactly one right triangle with integer sides.

The Prime Number Theorem [05/26/2008]

Let pi(x) be the number of primes below x. In a book I read, two formulas are given with identical right sides but the two left sides are pi(x) and pi(x) - pi(sqrt(x)) + 1. How can those two expressions be the same so that both formulas are true?

Prime Proofs [10/08/2002]

If a^(n) - 1 is prime, show that a=2 and that n is a prime. If a^(n) + 1 is a prime, show that a is even and that n is a power of 2.

Primes and Squares [05/03/2001]

For what values of prime number p is (2^(p-1)-1)/p a perfect square?

Primes Containing but Not Ending in 123456789 [02/26/2003]

Are there infinitely many primes that contain but do not end in the block of digits 123456789 ?

Primes of the Form 4n+3 [11/07/1999]

Prove that there are infinitely many primes of the form 4n+3 where n is an element of the natural numbers.

Primes: p+1 a Multiple of 6? [10/06/2002]

Prove that if p and p+2 are both prime, then p+1 is divisible by 6. Completely stuck on what to do.

Primitive Elements vs. Generators [05/24/2002]

Prove that x is a primitive element modulo 97 where x is not congruent to 0 if and only if x^32 and x^48 are not congruent to 1 (mod 97).

Primitive Pythagorean Triple Congruences [04/17/2003]

If x,y,z are primitive Pythagorean triples, prove that x+y and x-y are congruent modulo 8 to either 1 or 7.

Primitive Roots of Primes [06/05/2005]

I define the Primitive Roots Index (PRI) of a prime p as the [sum of all its p.r.’s] mod p. A surprising property of PRI which I stumbled upon is its value is always 0, + 1, - 1 for all primes. Is it possible to prove this property for all primes? Is it possible to derive the PRI as a function of the value of p?

Primitive Triples [04/24/2003]

In a primitive Pythagorean triple (x, y, z), why must x+y and x-y be congruent to either 1 or 7 mod 8 ?

Primorials [10/15/2003]

We know that p_1 * p_2 * ... * p_n + 1 is either prime or divisible by a prime not included in the list. But is the second condition necessary? Is the result ever not prime?

Probability of a Sum [08/16/2002]

If the integers m and n are chosen at random between 1 and 100, what is the probability that a number of the form 7^m + 7^n is divisible by 5?

Problem Posed by Fermat [05/04/2001]

Find a right triangle such that the hypotenuse is a square and the sum of the two perpendiculars, or indeed of all three sides, is also a square...

Product of Two Primes [10/27/1999]

How many positive integers less than 100 can be written as the product of the first power of two different primes?

Programs to Find Prime Numbers [11/27/1996]

Can a program be written in BASIC to compute the number of prime numbers smaller than n?

Proof by Induction [05/24/2002]

Prove by induction that (n^7 - n) is divisible by 42.

Proof: Infinitely Many Primes [6/24/1996]

I need a proof that there are an infinite number of primes other than Euclid's proof by contradiction. What is the Dirichlet proof?

Proof Involving Legendre Symbol [02/03/2003]

If p, q are both prime odd numbers such that they are not factors of a, and p=q(mod 4a), prove that (a/p)=(a/q).

Proof Involving mod 5 [10/27/2002]

Prove n^2 mod 5 = 1 or 4 when n is an integer not divisible by 5.

Proof of Irreducibility in Z_p[x] [11/03/2006]

Let f be a primitive polynomial in Z_[x]. For any prime p, let f_p be the image of f under the map Z[x]--->Z_p[x]. Then f is irreducible iff f_p is irreducible in Z_p[x] for some prime p.

Proof of Lagrange's Theorem [11/23/2000]

I am looking for a proof of Lagrange's Theorem, which states that any positive integer can be expressed as the sum of 4 square numbers.

Proof of No Integer Solutions for a^3 + b^3 = c^3 [02/08/2004]

In the equation a^3 + b^3 = c^3, how is it possible to prove that there are no integers that satisfy the equation?

Proof of the Compositeness Theorem [04/10/2005]

I have determined that there are no prime numbers in the interval [n! + 2, n! + n], but I am trying to make sense of why. Is there a theorem that expalins why this works?

Proof that 1 + 1 = 2 [06/10/1999]

Can you prove that 1 + 1 = 2?

Proof That Equation Has No Integer Roots [05/09/2000]

How can I prove that if p is a prime number, then the equation x^5 - px^4 + (p^2-p)x^3 + px^2 - (p^3+p^2)x - p^2 = 0 has no integer roots?

Proof That Product is Irrational [03/28/2001]

How can I prove that the product of a non-zero rational number and an irrational number is irrational without using specific examples?

Page: [<prev]  1  2  3  4  5  6  7  8  9 [next>]