1
vote
0answers
46 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
0
votes
1answer
35 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
3
votes
1answer
69 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 ...
0
votes
2answers
355 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
6
votes
1answer
46 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
3
votes
1answer
61 views

If $k$ is an odd number then $3k^2 +16$ is not a perfect cube

I am pretty sure that the title is true. Could anybody please prove it? I am particularly interested in a proof that mostrly relies on divisibility.
1
vote
3answers
41 views

Prove that $(k.n)!$ is divisible by $(k!)^n$

Suppose $k,n$ are integers $\ge1$. Show that $(k.n)!$ is divisible by $(k!)^n$ I have simplified the problem and now, I need to prove that any $k$ consecutive integers is divisible by $k!$. However I ...
1
vote
2answers
79 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
0
votes
1answer
38 views

What are the smallest numbers $n$ such that $\dfrac{d(n)}{\ln(n)} \geq k$ where $d(n) = \sigma_0(n)$ is the number-of-divisors function?

I have calculated $\dfrac{d(n)}{\ln(n)}$ on a few highly composite numbers up to 5040. Here is what I got: $\dfrac{d(120)}{\ln(120)} = 3.3420423$ $\dfrac{d(360)}{\ln(360)} = 4.0773999$ ...
0
votes
1answer
28 views

Remainder of trick-number divided by 9

How can I calculate the remainder of something like $199\cdot 741934^{1234}$ by 9?
0
votes
2answers
75 views

Prove that if $n^2 - 1$ is divisible by a prime number $p$ such that $n - 1$ is not divisible by $p$, then $n + 1$ is also divisible by $p$.

If this proposition is false, please give at least $3$ counter-examples, and try to modify the proposition so that it becomes true. If the proposition is true, please try to prove this even more ...
2
votes
3answers
156 views

Find positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$

Find all positive integers $(x,n)$ such that $x^{n} + 2^{n} + 1$ is a divisor of $x^{n+1} +2^{n+1} +1$ I encountered this question in one of my monthly assignments. Unfortunately, I don't know ...
2
votes
2answers
113 views

Greatest common divisor with one parameter and condition

I have this homework question: Find $d = \gcd(10x+6, 3x+1) $ where $d > 5$ and $x$ is natural How can I solve it?
0
votes
1answer
71 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 ...
1
vote
1answer
126 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 ...
2
votes
3answers
95 views

Is it true that $5^k \mid f(5^k)$?

I guess if it is true that $5^k \mid f(5^k)$, where $f(n)$ denotes the $n$-th Fibonacci's number. I have tried to prove it by induction on $k$, but nothing. Have you got any ideas?
2
votes
1answer
44 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that ...
1
vote
1answer
38 views

How to prove $D(n)<2n(\log\log n)$?

How to prove $D(n)<2n(\log\log{n})$ for all sufficiently large $n$ where $D(n)$ is the Divisor summatory function.
1
vote
1answer
85 views

How many regulars do the primorials 223092870 and 6469693230 have?

Regulars = Divisors + Semidivisors http://global.britannica.com/EBchecked/topic/496213/regular-number So for example: 6 has 5 regulars: 1, 2, 3, 4, 6. 8 has 4 regulars: 1, 2, 4, 8. 9 has 3 ...
0
votes
0answers
67 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 ...
2
votes
2answers
116 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 ...
0
votes
1answer
31 views

Number Theory Divisibility Question

(From Math Challenge II Number Theory packet) Given that $a,b,n$ are positive integers. Assume that for any positive integer $k\neq b, (k-b)\mid(k^n-a)$, the which of the following must be true? ...
0
votes
2answers
51 views

If a natural number $x$ is divisible by $3$

Is the sentence If a natural number $x$ is divisible by $3$ then, if it is not divisible by $3$ then it is divisible by $5$ true or false?
0
votes
2answers
54 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
2
votes
1answer
65 views

Factors of a perfect square plus one

For large integer $a$, small integer $d$, consider the following quantity: $$a^2+d$$ What are the best lower bounds one can get for the sum $l+m$, where integers $l,m$ are such that: $$lm=a^2+d$$ ...
1
vote
0answers
26 views

Using $ \gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$ for GCD?

It should be true that $\gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$. But: How can I use this equality to compute the GCD of $a$ and $b$? It seems as if $r$ is of the form $r = k\cdot b + s$ ...
0
votes
1answer
65 views

Pythagorean quadruple generators with a gcd relation

For non-negative integers $m,n,q,p$ with $\gcd(m,n,q,p)=1$, assume we have: $$\gcd(mq+np,b)=|nq-mp|$$ for some integer $$b<mq+np$$ and that $$8\nmid\,mq+np,$$ $$m+n+p+q\equiv 1\mod 2.$$ Can ...
1
vote
1answer
52 views

Greatest Common Divisor Divisibility Question

Can we characterize the pairs of positive integers $b<a$ such that: $b|(a^2+\gcd(a,b))$
4
votes
5answers
115 views

To find relatively prime ordered pairs of positive integers $(a,b)$ such that $ \dfrac ab +\dfrac {14b}{9a}$ is an integer

How many ordered pairs $(a,b)$ of positive integers are there such that g.c.d.$(a,b)=1$ , and $ \dfrac ab +\dfrac {14b}{9a}$ is an integer ?
0
votes
6answers
95 views

If $n$ is a perfect square and a perfect cube then $7$ divides $n(n-1) $

If a positive integer $n$ is both a perfect square and a perfect cube , then is it true that $7$ divides $n(n-1)$ ?
1
vote
2answers
30 views

$3^a\mid s(n) \Rightarrow 3^a\mid n$

This is not a homework question, neither a championship problem (as far as I've searched in the net), and it came up noticing a singular pattern, involving the powers of $3$: "Prove or disprove that ...
0
votes
1answer
30 views

Number theory question maximum possible difference between $a$ and $b$

$1287a 45b$ is a 8-Digit number, where $a$ and $b$ are not zero. The number is divisible by 18. What is the maximum possible difference between $a$ and $b$? My solution: I first said since it's ...
1
vote
5answers
89 views

prove that $3$ does not divide $n^2+1$

How do I prove that $3$ does not divide $n^2+1$, for all $n\in\mathbb{Z}$, thought of in separate cases, but did not get, induction also was unable to ....
0
votes
2answers
68 views

If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$?

If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$? I am shamelessly asking how to solve the problem? I have no idea how to start and solve. Please help.
1
vote
1answer
59 views

Solve a system of diophantine equations

I have a problem with elemental number theory. I started with the expression $$ (a - \frac{1}{b})(b - \frac{1}{c})(c - \frac{1}{a}) $$ and task to find all natural $a,b,c$ so that the result of the ...
0
votes
0answers
25 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 ...
1
vote
1answer
35 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.
-2
votes
3answers
131 views

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

What is an intuitive way to think about odd and even numbers? And about divisibility also...
1
vote
1answer
21 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 ...
8
votes
1answer
105 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 ...
1
vote
1answer
58 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 ...
-1
votes
3answers
65 views

If $2$ divides a number $a$, does $2^n$ divide $a$ ? $n$ is any integar

If $2$ divides a number $a$, does $2^n$ divide $a$ ? $n$ is any integer. This seems to be true for me, but I just want to make sure it applies for all numbers. example if a = 137 2 does not divide ...
4
votes
1answer
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 ...
0
votes
2answers
18 views

prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$

Prove that $\forall k\in \mathbb Z$ if $(m,n)=1$(coprimes) then $(k,m,n)=1$ I did this by contradiction: let $d=(k,m,n)$ so that $d\neq 1$; by definition of greatest common divisor $d|k, d|m, d|n$ ...
1
vote
5answers
33 views

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$

if $gcd(a,b)=gcd(a,b,c)$ then I need to prove that $ax+by=c$ has solution in $\mathbb Z$ that is: $gcd(a,b)|c$ but how can I prove it with the given hypothesis?
3
votes
1answer
137 views

Proof of $(ma+ nb, mn)=(a,n)(b,m)$

Let $a,b,m,n \in \mathbb Z$. If $(m,n)=1$ ( $m,n$ are coprime integers) prove that $(ma+ nb, mn)=(a,n)(b,m)$ I started the proof like this: Let $c,d,e$ be the greatest common divisors of ...
0
votes
4answers
153 views

What is the remainder when 4 to the power 1000 is divided by 7

What is the remainder when $4^{1000}$ is divided by 7? In my book the problem is solved, but I am unable to understand the approach. Please help me understand - Solution - To find the ...
0
votes
2answers
33 views

GCD of two real numbers

How would I show that gcd($2a+1 , 9a+4)=1 $? Here $a$ is an integer. I used the definition of the greatest common divisor, but felt it is too lengthy.
2
votes
1answer
36 views

Biggest common divisor

Find the GCD of all the numbers from the set $$\{(n+2014)^{n+2014}+n^n\mid n\in \mathbb{N},n>2014^{2014}\}$$ Now I have the proof but i can't understand one thing Lets say $d$ is the GCD.Now let ...
1
vote
2answers
44 views

Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof. So, I ...