10
votes
5answers
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, ...
4
votes
4answers
215 views

What is easiest way to know it the large number divisible by 57

What is the easiest way to know if large number is divisible by 57? For example, how could I deduce that 57 divides 300000177?
2
votes
4answers
70 views

Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$? [duplicate]

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$. original question : prove ...
1
vote
7answers
50 views

$\operatorname{gcd}(ab,a+b)=1$ if $a$ and $b$ are relatively prime

I'm trying to show that if $\operatorname{gcd}(a,b) = 1$, then $\operatorname{gcd}(ab,a+b)=1$. I've tried to use the gcd properties: $$\operatorname{gcd}(a,b)=1 \implies ...
4
votes
1answer
56 views

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime Progress If $a^2+b^2$ is prime then it is already proved, ...
1
vote
1answer
37 views

If $n$ is any positive integer whose last digit is $5$, then $5$ divides $n$

Prove that if n is any positive integer whose last digit is a 5, then 5|n Therefore, n is going to be 5, 15, 25, 35 etc ... b∣a states that 'b divides a' and we know that 5∣5, 5∣15, 5∣25, 5∣35 ...
6
votes
3answers
92 views

If $n=3^{2^k}-2^{2^k}$, then $n\mid 3^{n-1}-2^{n-1}$

Let $k \in \mathbb{N}$ and let $n=3^{2^k}-2^{2^k}$. Show that $$n\mid 3^{n-1}-2^{n-1}.$$ I have no idea how to prove this. Any suggestions?
3
votes
2answers
56 views

Induction on GCD problem [duplicate]

This is a two part question Given $\gcd(a,b) = 1$ consider $$\gcd \left( \frac{a^n - b^n }{a-b}, a- b\right) $$ It appears that the value of this is always equal to $n$ or $1$. How to prove it? ...
-1
votes
2answers
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, ...
0
votes
1answer
28 views

Check my proof : gcd(a,b)=1=gcd(x,y) => (xa,yb)=gcd(x,b) gcd(y,a)

Note: (x,y) means gcd(x,y) I managed to prove the next Proposition: Let $(a,b)=1=(x,y)$. Then $(x a,y b)=(x,b)(y,a)$. It can be easily be generalized for the case that $(a,b)\neq1$ and or ...
0
votes
4answers
91 views

Find a pair of integers $n,x$ such that $84 = nx + (n-1)n$ and $x$ is odd [closed]

I have a equation like this: $$84 = nx + (n-1)n$$ where, $x$ is odd. I need to find the fastest way to find a possible $n$ and $x$. (In this case: $n = 6, x = 9$) Edit: Maybe the background ...
1
vote
3answers
103 views

Number theory proofs regarding gcd's

How would you prove if $ad-bc = 1$, then $(a+c,b+d)=1$
2
votes
3answers
146 views

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
2
votes
2answers
78 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
1
vote
3answers
71 views

Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
1
vote
3answers
44 views

If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$

As stated in the title, the problem to prove is Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$. I think I've proved it, but I would like a second opinion. Here ...
0
votes
2answers
64 views

Divisibility crieteria

This is a follow-up question. The problem is: Given two natural numbers, $m$ and $n$, and $n \vert m^2$. Find necessary and sufficient conditions for $n \vert m$. Here are what I find: ...
1
vote
0answers
47 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 ...
1
vote
1answer
47 views

Question in elementary number theory

I have a question. Suppose that $a$ and $b$ are two natural numbers so that $ a<b$ and $ a\nmid b$. Put $ d=ka$, where $ k\not=0,1,t\dfrac{b}{\gcd(a,b)}$, for $ t\geq 1$. I want to prove that $ ...
3
votes
5answers
591 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
0
votes
1answer
22 views

Position of switches based on divisibility

There is a set of $1000$ switches. Each has four different positions, called $A$, $B$, $C$, and $D$. When the position of any switch changes, it is only from $A$ to $B$, from $B$ to $C$, from $C$ to ...
0
votes
2answers
64 views

Find all values of for which the ratio is an integer

Find all values of $n$ for which, $$\dfrac{(\dfrac{n+3}{2}) \cdots n}{(\dfrac{n-1}{2})!}$$ is an integer. I have tried the problem for some primes. Each time it seemed true. But I still ...
1
vote
2answers
36 views

GCD question involving coprimes

How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$? By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and ...
0
votes
1answer
17 views

Proving $k$ is a common divisor of $a$ and $b$ iff $k\,|\gcd(a,b)$ — converse

I'm currently trying to solve the converse of this statement is true after proving the normal version is true. If $k$ is a common divisor of $a$ and $b$, then $k \,| \gcd(a, b)$ So far I know the ...
2
votes
1answer
20 views

Questions relating to gcd

Assume a, b and c are positive integers. 1) Suppose that a | b. Show that gcd(a, c) ≤ gcd(b, c). 2) Suppose that a ≤ b. Is it necessarily true that gcd(a, c) ≤ gcd(b, c)? I'm having trouble with ...
3
votes
1answer
63 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
1answer
42 views

Prove that $f(n,p)$ is a non-square integer

Let, $$f(n,p)=(n+1)(n+2) \cdots (n+p-1)$$ Then show that $f(n,p)$ is a not a perfect square for all $n \in \mathbb{N}$ and for all odd primes $p$. Consider only the cases when ...
2
votes
5answers
69 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
0
votes
2answers
36 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
0
votes
2answers
64 views

Prove or disprove this implication

Prove or disprove: If $x, a, b > 0$ are integers such that $$\gcd(x-a, x+b) = 1\ \ \mbox{and}\ \ \gcd(2x-a, x+b) > 1,$$ then $$a+b = x.$$
2
votes
1answer
44 views

$[n,n+1]=\text{ ??????}$

I know the answer is $n(n+1)$, but I'm having trouble formulating an argument. I know by the definition, if I let $h=[n,n+1]$ $$h=nk_1, h=(n+1)k_2$$ $$nk_1=(n+1)k_2$$ ...
4
votes
2answers
84 views

For every integer, some multiple of it is of the form $99 \ldots 900 \ldots 00$

The goal is to prove that for every positive integer $ z$ there exists a positive integer $a$ such that $az = 99 \ldots 9900 \ldots 00$. Let $a = \frac {99 \ldots 9900 \ldots 00}{z}$ That ...
0
votes
1answer
39 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$ ...
2
votes
2answers
34 views

highest power of prime $p$ dividing $\binom{m+n}{n}$

How to prove the theorem stated here. Theorem. (Kummer, 1854) The highest power of $p$ that divides the binomial coefficient $\binom{m+n}{n}$ is equal to the number of "carries" when adding $m$ ...
0
votes
1answer
19 views

$B$-powersmooth number divides $\mathrm{lcm}(1,2,3,\ldots B)$

Let $M$ be $B$-powersmooth (ie. all prime powers in $M$'s factorization are $\le B$). I want to prove that $M \mid \mathrm{lcm}(1,2,3,\ldots, B)$. I thought it would be easy to prove this using ...
1
vote
1answer
40 views

$nc_i\mid\prod_{i=1}^3(nc_i+1)-1$ iff $\exists c\in 6\mathbb{N}:c_i=ic$

Let $c_1<c_2<c_3$ be natural numbers and $$C_n=\prod_{i=1}^3(nc_i+1)-1\;\;\;\;\;(n\in\mathbb{N})$$ I want to show that it holds $$\forall n\forall i : nc_i\mid ...
0
votes
2answers
86 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
158 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 ...
4
votes
1answer
128 views

$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$ isn't divisible by 5

I have no idea Prove that for any $n$ natural number this sum $$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$ isn't divisible by $5$. $\begin{array}{l} \left( {1 + x} \right)^{2n + 1} - ...
0
votes
1answer
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 ...
1
vote
1answer
169 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 ...
0
votes
1answer
77 views

Have you seen this theorem before? (GCD divides, neccessary & sufficient condition)

Conjecture. Let $a,b, c\in \Bbb{Z}, b \neq 0$, The following conditions are equivalent: (1) $d = \gcd(a,b)$ divides c. (2) There's a polynomial in $f \in \Bbb{Z}[X,Y]$ with $c$ constant term, such ...
-1
votes
3answers
112 views

Prove that if $n+1$ is divisible by $m$ then $n^2-1$ is also divisible by $m$. [closed]

Prove that if $n+1$ is divisible by $m$ then $n^2-1$ is also divisible by $m$. And prove that if $n^2-1$ is divisible by $m$ then $n+1$ is also divisible by $m$.
2
votes
3answers
79 views

If $3$ divides $q^3$, is it true that $3$ divides $q$?

I think this is true because of prime factorisations, i.e. If $3$ a factor of the prime factorisation of $q^3$, then $3$ is a factor of the prime factorisation of $q$. Therefore If $3$ divides ...
1
vote
2answers
73 views

Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$

I'm trying to prove that all integer solutions $a > b \ge 0$ to the divisibility condition in the title, namely $$(a^2+b^2+1) \mid 2(2ab+1),$$ are given by ...
0
votes
0answers
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 ...
0
votes
1answer
28 views

For how many values of $a,b,c\in(1,2\ldots,p-1)$ does $p$ | $({a^2}-bc)$ where $p$ is an odd prime number

In a mock test for an entrance exam I am preparing for came the following question: Let $p$ be an odd prime number and $T_p$ be the following set of matrices $$ T_p= \left( ...
0
votes
1answer
44 views

Verify my proof on elementary number theory

I've tried to prove this theorem, which is very simple, but is a kind of practice for me. Let $a,b$ be two positive integers. Therefore, if $a+b$ is a composite number, $frac(\frac{a}{l}) + ...
0
votes
0answers
56 views

Vieta jumping with non-monic polynomials

I have recently discovered Vieta jumping as a problem-solving technique. In order to teach myself about it, I have located most (all of?) the standard references, both here on MSE and "out there" (via ...
0
votes
0answers
35 views

The elegant expression in terms of gcd and lcm - algebra - (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to ...