# Tagged Questions

2k views

### Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16… alternate between prime and composite

I am working through an elementary number theory book and I have come across the following problem. Show the following claims are wrong: Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ...
87 views

### Fastest way to find if a given number is prime

Given a random number, what would be the quickest possible way of finding out whether it was prime? Obviously, one could just iterate through the number in order to see if it was divisible by ...
105 views

### Why is $y^{x-1}-1$ divisible by $x$?

I wanted to know if there is a way to prove that $y^{x-1}-1$ is divisible by $x$. Where $x$ is a prime number and is not equal to $y$, and $y$ is any positive whole number besides $1$. For example, ...
34 views

### A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
26 views

### Length of smallest repunits divisible by primes

I want to prove this statement from Wikipedia: It was found very early on that for any prime p greater than 5, the period of the decimal expansion of 1/p is equal to the length of the smallest ...
65 views

### Characterizing the primes which don't divide any Pell-Lucas number(s)

For integer $n$, let $P_n$ be a Pell number, and $Q_n$ its companion. Is there a characterization of the prime numbers $p$ which don't divide any $Q_n$? By brute-force search, I found that this ...
76 views

### Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
56 views

### The binomial coefficients $\binom{n}{ p}$ are divisible by a prime $p$ only if $n$ is a power of $p.$

I'm looking for a "high school / undergraduate" demonstration for the: All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ ...
47 views

### If there is an $a\in\mathbb{Z}$ with $a^{n-1}\equiv 1\mod n$ but $a^{\frac{n-1}p}\not\equiv 1$ for all primes $p\mid n-1$, then $n$ is a prime

Let $n\in\mathbb{N}$ with $n\ge 3$ and $a\in\mathbb{Z}$ such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ ...
80 views

### Why does the number of divisors of a superior highly composite number is always a highly composite number up to 720720 ? (the only exception is 120)

I've calculated the number of divisors of every superior highly composite number up to $10^{27}$: http://oi59.tinypic.com/ndaijo.jpg The number of divisors of a superior highly composite number is ...
168 views

### Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
69 views

### Among the superior highly composite numbers, which are the most divisor dense numbers?

I’m searching for the most divisor dense natural numbers. Firstly we have the highly composite numbers: 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, … But ...
119 views

### Asymptotic divisor function / primorials

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial), and $\sigma(n)=\sum_{d|n}^{}d$ (divisor function). Could someone please tell me what the general asymptotic of $\dfrac{\sigma(p_n\#)}{p_n\#}$ is? It ...
40 views

### Prove that if m is prime and m|kl then either m|k or m|l.

Proofs homework question, here's what I've figured out thus far. Suppose m doesn't divide k. We need to then prove that m|l. If m doesn't divide k and m is a prime then we know m and k are co-prime ...
27 views

### How to apply the generalised divisibility rule to numbers of the form $10^k+n$

This is kind of a long question but bear with me. There's actually a question mark at the end. I'm trying to apply the generalised (decimal) divisibility rules to numbers of the form $10^k+n$ where ...
61 views

### Coprimality of $2^n + 3^n$ and $5^n + 7^n$

Prove or disprove that for all positive integers $n$, $2^n +3^n$ and $5^n + 7^n$ are always coprime. This is not a homework problem, it is merely a problem I set myself after doing some number theory ...
110 views

### Primality of the number of obtained by concatenating the n consecutive digits

Let $f_n$ be the number obtained by concatenating the first $n$ numbers (in base 10). For example $f_1 = 1, f_3 = 123$ and $f_{13} = 12345678910111213.$ Now if $n$ is even or divisible by $5$ then ...
37 views

### greatest common divisor of two primes a,b

Here is the question I am trying to prove: If $a,b$ are relatively prime and a>b prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are ...
117 views

### Primes $p$ such that $p^2$ divides $x^2 + y^2 + 1$

Call a prime $p$ awesome if there exist positive integers $x$ and $y$ such that $p^2$ divides $x^2+y^2+1$. Observation: $2$ is not awesome, because $x^2+y^2+1\not\equiv 0$ (mod $4$). But $3$ is ...
84 views

### Bezouts Identity for prime powers

I have two prime powers $2^n$ and $5^n$ for some arbitrary $n$. Their gcd is $1$ but how do I get their integer linear combination which is $1$ in terms of $n$. In other words what will be the ...
18 views

74 views

### Divisibility of prime numbers

I have this exercise in my worksheet in the discrete mathematics course.I don't understand the part that deals with prime numbers in integer-divisibility. "Show that for a prime number $p$, if a ...
148 views

### “Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
64 views

### What is the highest power of a prime that divides nPr?

I know that the highest power of a prime which divides $n!$ is given by $$\left[\frac np\right]+\left[\frac n{p^2}\right]+\left[\frac n{p^3}\right]...$$ Where $[x]$ is the greatest integer function. ...
85 views

### Why does $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ have new divisors $59$ and $509$ all of a sudden?

I am a noob when it comes to math so please bear with me. Why $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ has $2$ new divisors $59$ and $509$. I mean, all of its divisors are prime factors and ...
43 views

### GCD's and Proofs

Let p and q be odd primes. Prove that gcd(p + q, p - q) = 2. I have considered EEA to multiply it out, but I'm unsure where to go from there.
69 views

### Methods for finding a relatively prime integer

Here's the problem: Given a prime $p$ and an integer $x$, find an integer $c$ such that $gcd(x+c,p\#)=1$ where $p\#$ is the primorial for $p$. It is straight forward to solve this problem using ...
65 views

### Number theory proof with modular arithematic [closed]

What is the proof for: If p is an odd prime, show that $$1^n+2^n+3^n+...+(p-1)^n \equiv 0 (\mod p)$$ if $p-1$ does not divide $n$ or $\equiv -1 (\mod p)$ if $p-1$ divides $n$.
86 views

### When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
91 views

### How to show the existence of a number with certain divisibility conditions between two multiples?

How can we show that between two even natural numbers they're exists a natural number that isn't even? How can we show that they're exists a natural number that is odd and not divisible by 3, between ...
166 views

### The proportion of numbers not divisible by prime numbers with respect to primorial numbers.

Looking at the interval of the natural numbers $[1, p_{n}$#$]$; $\frac{1}{2}$ of the elements of this set will be even, and $\frac{1}{2}$ will be odd. $\frac{1}{3}$ of the elements of this set will ...
75 views

### A question on primes and divisibility

The question goes as follows: Prove that for any prime $p\geq 5$, $p^2-1$ will be divisible by $12$. I think I have a solution but I just wanted to double check with you guys. My attempt: If $p$ ...
478 views

### Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. [duplicate]

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. This is what I got so far. I figured that since $p,q$ are bigger than $5$, there are only odd primes for this conjecture. ...