This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms (1)

1
vote
1answer
161 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 ...
10
votes
5answers
1k 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, ...
3
votes
2answers
62 views

A non-UFD such that $a^2 \mid b^2$ does not lead to $a\mid b$

Is there any non-UFD that is a commutative ring such that $a^2 \mid b^2$ does not always lead to $a\mid b$? It would be preferable if examples are something that does not involve ...
4
votes
4answers
211 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
69 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 ...
2
votes
1answer
98 views

When does $2^n+n \mid 8^n+n$?

How to find all positive integers $n$ such that $2^n+n$ divides $8^n+n$ ?
1
vote
4answers
25 views

How to find a modular multiplicative inverse when GCD is not 1

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've ...
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 ...
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 ...
9
votes
1answer
92 views

For what integers $n$ is this divisibility statement true?

The statement being $$n^2 + 2 \mid 2014n + 2$$ The answer is $n = -2, 0, 1, 2014$. Don't know how to arrive at this answer without using comp sci. (Using the compsci answer, we can restrict the ...
3
votes
2answers
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 ...
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, ...
2
votes
1answer
21 views

prove by contradiction that $ax+by=c$ has no integer solutions if $c$ does not divide into $\gcd (a, b)$

Prove by contradiction that (the diophantine equation) $ax+by=c$ has no integer solutions if $c$ does not divide into $\gcd (a, b)$. Here is what I did: lets assume $c$ divides into $\gcd (a, b)$. ...
2
votes
2answers
25 views

Prove that the Diophantine equation $ax+by=c$ has no integer solutions if $\gcd(a,b)$ does not divide $c$

Prove that the Diophantine equation $ax+by=c$ has no integer solutions if $\gcd(a,b)$ does not divide $c$ there was a hint which is use use contradiction.
2
votes
1answer
40 views

How prove $n|2^{\frac{n(n-1)}{2}}\cdot (2-1)(2^2-1)(2^3-1)\cdots (2^{n-1}-1)$

Question: Today, when I solve other problem, I found this follow interesting result $$n\mid\left(2^{\frac{n(n-1)}{2}}\cdot (2-1)(2^2-1)(2^3-1)\cdots (2^{n-1}-1)\right),n\ge 1$$ It is clear ...
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
91 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?
-2
votes
1answer
54 views

The greatest common divisor of several numbers is the least positive integer that is their linear combination [closed]

Problem Show that the greatest common divisor of the integers $a_1, a_2, ..., a_n$, not all $0$, is the least positive integer that is a linear combination of $a_1, a_2, ..., a_n$. Remarks The ...
5
votes
2answers
172 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
1
vote
4answers
29 views

Evaluating the greatest common divisor.

I have a homework question which i'm struggling with, i would be interested in what method i should use to solve the following problems: ...
3
votes
1answer
268 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
1
vote
1answer
241 views

Is there a simple algorithm I can use for this?

if I were asked to find all integers between 1 and 100 that leave remainder 3 on division by 5 and leave remainder 4 on division by 7, how would I go about this? It seems like such a simple question ...
-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
2answers
35 views

A formula for a sequence which has three odds and then three evens, alternately

We know that triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36... where we have alternate two odd and two even numbers. This sequence has a simple formula $a_n=n(n+1)/2$. What would be an example ...
1
vote
2answers
52 views

Is it true that for any natural number $p$, if $p$ divides $ab$, then it divides either $a$ or $b$?

I need someone to check my answer. True or False ? For any natural numbers $p$, if $p$ divides the product $a.b$ of two natural numbers $a$,$b$ in $\mathbb{N}$, then either $p$ divides $a$ or $b$. ...
3
votes
0answers
75 views

Prove the equality

Given $a,b,c,d$ are positive integers such that $a^2+b^2+c^2+d^2-ab-bc-cd-da$ is divisible by $abcd$. Prove that $a=b=c=d$.
1
vote
2answers
75 views

How many possible combinations are there of these 4 numbers to add to multiples of 4?

If I have the numbers 0 1 2 and 3, how many combinations of any size but maximum of 4 add to a multiple of 4? EG: 0000 = 0 ( so 0*4), 1111 = 4, 0000 = 0 ( so 0*4), 0112 How many combinations ...
3
votes
2answers
102 views

Making a $m*n$ chocolate bar out of $1*k$ chocolate bars

So I've been puzzled by this problem for some time now: Suppose we have a chocolate bar with dimensions $m*n$ and it is made up out of finite number of $1*k$ chocolates. Proof that for any natural ...
4
votes
1answer
267 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
3
votes
4answers
64 views

Proving that (4-2/1)(4-2/2)…(4-2/n) in an integer.

We have to prove that $(4-2/1)(4-2/2)...(4-2/n)$ is an integer for $n\in\mathbb{N}$. Can we do this by induction? We prove for $n = 1$, which is trivial as $(4-2/1) = 2$ which is clearly an integer. ...
2
votes
2answers
40 views

Coprime Integers Proof Check

$\gcd(a,b)=1$ if and only if there is no prime $p$ such that $p|a$ and $p|b$ Prove it. So I went about doing it through contradiction: If $p|a$ and $p|b$ then $p|(x_{1})(x_{2})(x_{3})...$ where ...
1
vote
4answers
41 views

How to prove that for all positive integers $a,b$, if $a|b$ , then $\gcd(a,b) = a$?

I don't believe there are any counter examples that can be used for this (I think it is true). Could someone help me prove it? I understand why it's true (if I was right about that), but the proof ...
0
votes
3answers
40 views

How to make every integer out of $5k + 8q$?

Expression given: $N = 5k + 8q$ ($k$ , $q$ integer). Prove that we can make any integer from this expression. For example: $0= 5\cdot0+8\cdot0$; $5 = 5\cdot1+8\cdot0$; $3 = 8\cdot1 +5 ...
2
votes
1answer
74 views

The factors of $5^n-3^n-2^n$

I have been assigned the following question. Let $f(n):= 5^n-3^n-2^n$. Prove that (a) $p$ divides $f(p)$ for each prime $p$; (b) $p^{k+1}$ divides $f(n)$ for $n=p^k$, with $p=2,3,5$ and ...
2
votes
3answers
91 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
3
votes
7answers
350 views

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$ I can not understand how to prove it. Please help me.
0
votes
2answers
24 views

Multiplicity of roots in finite fields of order prime. [closed]

I am having trouble with completing this question from last years exam (part a and d) Let p be a prime, and $f = x^5-1 = (X-1)(X^4+X^3+X^2+X+1) \in \mathbb{F}_p[X]$ Show: (a) if $p\neq 5$ then every ...
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
vote
3answers
128 views

The number $n^4 + 4$ is never prime for $n>1$

I am taking a basic algebra course, and one of the proposed problems asks to prove that $n^4 + 4$ is never a prime number for $n>1$. I am able to prove it in some particular cases, but I am not ...
3
votes
3answers
198 views

Proving that $\gcd(n!,\ n+1)=1$ or $n+1$

For any positive integer $n$ I need to prove that $\gcd(n!,\ n+1)=1$ or $n+1$ (except one integer). I need to prove both cases and for which $n$ exactly it exists. I tried to use many gcd properties ...
1
vote
0answers
33 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. ...
1
vote
2answers
330 views

Show that the gcd of an odd integer and an even integer is odd

I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...
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
1answer
65 views

The product of three consecutive natural numbers is divisible by $6$

Please give me feedback for my answer to this question. Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by $6$ My answer: True. Suppose $n$ is ...
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 ...
1
vote
2answers
224 views

Proving that if $(a,b)=1$, then $(a, b+1)=1$

Problem If $(a,b)=1$ then $(a, b+1)=1$. Progress So far I have, Let $d = (a,b)$ Which implies $d\mid a$ and $d\mid b$ Which implies there exist $x$ and $y$ such that $d\mid (a)(x) + (b)(y)$ So ...
-1
votes
3answers
31 views

Easy question but tough judgement -Are both boundary points included in a time interval as in this question

So the question is - Six bells commence tolling together at intervals of 2,4,6,8,10 and 12 seconds respectively In thirty minutes how many times do they toll together? (A) 16 (B)15 This question is ...
-1
votes
1answer
107 views

Understanding a proof of the fact that $\binom{n}{k}$ is always a natural number.

Original source of question and solution. Question is on the left, answer is on the right. Question: Notice that all the numbers in Pascal's triangle are natural numbers. Use part (a) to prove by ...
0
votes
4answers
29 views

If GCD of x and y is G then GCD of x and x+y is also G. but how to prove it? [closed]

If GCD of x and y is G then GCD of x and x+y is also G but how to prove it?
2
votes
4answers
150 views

Divisibility by seven

Given number n, whose decimal representation contains digits only $1, 6, 8, 9$. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7. If number is m ...