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

learn more… | top users | synonyms

5
votes
5answers
314 views

Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

Somewhere on Stack Exchange I saw the equation $$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$ I had never seen this before, so I started trying to prove it. Without success... Can anyone explain me (so ...
2
votes
1answer
113 views

Prove that $\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a,b)} - 1$ [duplicate]

I have two questions about a prove that I have to do for my mathematic study. I'm now thinking about it the whole day, but can't find the prove. Let $a,b \in \mathbb Z_{>0}$. (a) Prove: ...
1
vote
3answers
51 views

Greatest Common Divisor property: If $\gcd(a, b) = 1$ and $a | c$ and $b | c$, then $ab | c$ [duplicate]

Here is what I am trying to prove: Let $a,b,c,d \in ℤ_+$ with gcd$(a,b)=1$. If $a|c$ and $b|c$, prove that $ab|c$. Does the result hold if gcd $(a,b)\neq 1$ ? I know that gcd $(a,b)=1$ can be ...
2
votes
1answer
80 views

How to calculate “gcd product” $\operatorname{gcdp}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$

Given two numbers $m$ and $n$ how can we calculate the gcd product of any two numbers i.e, $\operatorname{gcd p}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ where gcd is the greatest common divisor? Can ...
0
votes
2answers
86 views

Are $\frac{a}{\gcd(a,n)}$ and $n$ always relatively prime?

If $d = \gcd(a,n)$, must $\dfrac ad$ and $n$ be relatively prime? Prove or disprove. Do I show that they need to be relatively prime and then the inverse that they do not need to be relatively ...
1
vote
4answers
48 views

Evaluating the greatest common divisor of pairs $(a, a^2)$, $(a, a+1)$, $(a, a+2)$

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: ...
5
votes
4answers
319 views

Prove or disprove statements about the greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
1
vote
2answers
183 views

Proof of Euclid algorithm — divisor of $m$ and $n$ must divide $m - qn$

In Knuth's book "The Art Of Computer Programming Vol.1" there is a description about Euclid's algorithm to find the greatest common divisor of m and n. And there is a phrase. $m = qn+r$. If $r ...
0
votes
2answers
208 views

What can we say about $\gcd(a,b)$ if $as + bt = 2$ fo rsome $s,t \in \mathbb{Z}$?

I have a question I can not figure out (It's #2 in section 4.4 of the book Discrete and Combinatorial Mathematics, by Ralph P. Grimaldi). $\mathbb{Z}^+$ = The set of all positive integers ...
0
votes
2answers
29 views

Proving properties of Greatest Common Divisors

I have two questions I'm struggling with 1) Suppose that gcd(a, y) = 1 and gcd(b, y) = d. Prove that gcd(a · b, y) = d I have 1 = ua + vy and d = sb + ty, and I use linear combination to get ...
1
vote
1answer
29 views

Divisibility lemma: $\exists n_0\mid n,\,\, m_0\mid m,\,(n_0,m_0) = 1,\text{ and }\,[n_0,m_0] = [n,m]$

I want to prove that, in a commutative group, there always exists an element whose order is $\mathrm{lcm}$ of the orders of two other elements. The exercise indicates that it follows easily from the ...
0
votes
1answer
245 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}$: The number of divisors of a superior highly composite number is always a highly composite number up ...
2
votes
1answer
79 views

If $\gcd(r,s)=1$, which numbers can be written as a linear combination $as+br$ with $a,b$ nonnegative?

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+br$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
1
vote
2answers
137 views

Distinct Mersenne numbers are coprime

How can you prove that if $p$ and $q$ are distinct primes, then the following holds?: $$(M_p,M_q)=1$$ Note: $M_n=2^n-1$, with $n$ prime number
62
votes
13answers
22k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
9
votes
9answers
297 views

What is $\underbrace{555\cdots555}_{1000\ \text{times}} \ \text{mod} \ 7$ without a calculator

It can be calculated that $\frac{555555}{7} = 79365$. What is the remainder of the number $5555\dots5555$ with a thousand $5$'s, when divided by $7$? I did the following: $$\begin{array} & ...
3
votes
4answers
82 views

Proof of divisibility using modular arithmetic: $5\mid 6^n - 5n + 4$

Prove that: $$6^n - 5n + 4 \space \text{is divisible by 5 for} \space n\ge1$$ Using Modular arithmetic. Please do not refer to other SE questions, there was one already posted but it was using ...
1
vote
5answers
71 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
2
votes
2answers
90 views

Proving $310 \mid n^{121}-n$ for all integers $n$

I wrote it as $n^{120}=1\pmod{310}$ and thought I'd divide it in simpler congruences with primes (is this right?) $$n^{120}=n^{4\cdot30}=1\pmod{31}$$ $$n^{120}=n^{30\cdot4}=1\pmod{5}$$ But then I'm ...
3
votes
1answer
55 views

Deceptively simple divisibility problem

Suppose we are given integers $a,b$ with the condition that there exists a prime $k$ such that $$2a+b\mid (a+b)^k$$ What can we say about $\gcd(a,b)$? So far, I can see that for all primes $p:p\mid ...
-1
votes
1answer
484 views

Finding $GCD$ excluding some elements from an $array$ [closed]

I have an array of numbers. I want to calculate $GCD$ of all numbers but excluding numbers from particular index $a$ to index $b$. I need to repeat the same operation multiple times with different ...
0
votes
1answer
47 views

Confusion (Divisible, Multiples)

So the question is "How many numbers between $3$ and $101$ are exactly divisible by $4$?" I found out that the answer is $25$. When reading this question over, a thought came into my head. What if ...
5
votes
1answer
183 views

Prove Divisibility In Fibonacci Sequence Over A Prime Number

In The Fibonacci sequence which is defined as: Lets say we have the number $p$ which is an odd prime. Prove that: $F_{p-1} + F_{p+1} -1$ Is divisible by $p$. Prove that for any given $n$ real ...
3
votes
1answer
29 views

Are there positive integers $x, y$ and $z$ such that $2^{x} · 3^{4} · 14^{y} = 126^{z}$

Can anyone give me a tip on how to approach this. Possibly a theorem of some sort that allows me to work with powers using modular arithmetic. Thanks for the help.
0
votes
0answers
29 views

If no elements of a sequence $a_n$ are divisible by $\pi$, does $\forall n, a_n \mod \pi \in (0;\pi)$ hold?

Given a sequence like $a_n = n$ or $a_n = 50n$, (or any arbitrary constant), and that no element of the sequence is divisbile by $\pi$, would $b_n = a_n \mod \pi$ eventually take on all values in the ...
1
vote
0answers
38 views

On integer $n>1$ and prime $p$ such that $p<n$ , $p$ does not divide $n$ and $n-p$ is a prime

Let $n>1$ be a given integer and $p$ be a prime less than $n$ and not dividing $n$ ; so $p$ and $n$ are co-prime ; hence $n-p$ and $n$ are also co-prime ; I would like to ask when is $n-p$ also is ...
1
vote
1answer
50 views

Hints for solving this Number Theory problem on divisibility

Find all positive integers $d$ such that $d$ divides both $n^{2}+1$ and $(n + 1)^{2}+1$ for some integer $n$. Currently what I am thinking of is like manipulating $n^{2}+1$ and finding out the ...
3
votes
3answers
76 views

Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$

Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$ without the use of a calculator. It is clear that $2003^4+1$ has a $082$ at the end of its number so $2003^4+1$ only has one factor of ...
2
votes
3answers
138 views

Divisibility test by 7

Pohlmann-Mass method Step A: If the integer is 1,000 or less, subtract twice the last digit from the number formed by the remaining digits. If the result is a multiple of seven, then so is the ...
3
votes
5answers
143 views

Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$

Could you help me with the problem below? Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$. Thank you!
2
votes
1answer
93 views

On a proof that “there are at least $F_n$ Collatz permutations of length $n$”.

Let $n, k \in \Bbb{N}$ and $F_n$ be the $n$th term of the Fibonacci sequence. Let $u$ be the map $x \to 3x+1$ and $d$ be the map $x \to \frac{x}{2}$. Let a type be a sequence of $u$'s and $d$'s. ...
6
votes
1answer
81 views

How does the size of the set $A(R) = \{(a,b) \; | \; a,b \in N \times N, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$ grow?

How does the size of the set $$A(R) = \{(a,b) \; | \; a,b \in \mathbb{N} \times \mathbb{N}, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$$ grow as a function of $R$? My try: It's clear that $|A(R)| ...
2
votes
1answer
50 views

Question regarding gcd in polynomial ring over a field

Let $\mathbb{F}_q$ be a finite field. We have a polynomial ring $\mathbb{F}_q[t]$ and its field of fractions, which we denote $\mathbb{K}$. Suppose I have polynomials $f_1, \ldots, f_n$ in ...
3
votes
4answers
80 views

Solutions of $2^a - 7 = 27b$

How can I find the solutions of the equation $2^a - 7 = 27b : a, b \in \mathbb{N}$? I can see this is also of the form $2^a - 7 \equiv 0 \mod 27$.
0
votes
2answers
33 views

Verifying integer solutions to linear equations

Suppose I have the equation $B = \frac{8A - 29}{27}$, where $A$ and $B$ are integers. Then $27B = 8A - 29$, and so we have the linear Diophantine equation $8A - 27B = 29$. Using the extended ...
4
votes
5answers
83 views

An integer when divided by $5$ and $13$ leaves residues $4$ and $7$ respectively

Find an integer when divided by $5$ and $13$ leaves residues $4$ and $7$ respectively. (Without Modular Arithmetic). I don't know if it is right, but i got this $$n=5x+4=13y+7$$ ...
0
votes
1answer
40 views

Write a floored integer division in function of two divisions?

Is there any method to calculate the floored integer division for the sum of two numbers given the floored division of the summands, without splitting into cases? I know that, with floored division, ...
3
votes
1answer
23 views

Boundedness of $\gcd(|x-y|,|a_x-a_y|)$ in sequence

Let $a_1,a_2,\ldots$ be an infinite sequence of distinct positive integers, and let $n$ be a positive integer. Does there always exist integers $x,y$ such that $\gcd(|x-y|,|a_x-a_y|)>n$? When ...
2
votes
3answers
78 views

Find all intergers such that $2n^2+1$ divides $n^3+9n-17$

Find all intergers such that $2n^2+1$ divides $n^3+9n-17$. Answer : $n=(2 \ and \ 5)$ I did it. As $2n^2+1$ divides $n^3+9n-17$, then $2n^2+1 \leq n^3+9n-17 \implies n \geq 2$ So $n =2$ is ...
2
votes
1answer
29 views

When is it possible to find a relatively prime pair among $n$ numbers?

Suppose I have a set of $n$ numbers and their gcd is $d$. If I divide every number by $d$, is it possible to find a pair that is relatively prime? Intuitively yes, but how do I prove it? I tried ...
8
votes
1answer
58 views

Remainder when dividing by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$

Given a $54$-digit number consisting of only ones and zeros. Prove that the remainder when dividing this number by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$. The number can be written ...
2
votes
2answers
57 views

If $\gcd(a,n)=1$ then there exist integers $x,y$ such that $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y \pmod n$

If $a$ is integer and $n$ is positive integer such that $\gcd(a,n)=1$ then there exist integers $x,y$ for which $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y\pmod n$. By Dirichlet's principle I ...
4
votes
0answers
72 views

Extention of Euclid's GCD Algorithm. (The Art of Computer Programming, Volume 1, Edition 3, Section 1.2.1, Exercise 12)

Euclid's GCD algorithm which is used to find GCD of two input numbers, say, $c$ and $d$, needs the inputs to be positive integers. Exercise 12 provides an extension to this algorithm and allows $c$ ...
2
votes
2answers
152 views

Is a Number Divisible by 40

One of the "shortcuts" for determining if a number is divisible by 8 is to see if the last three digits are divisible by 8. One ...
0
votes
5answers
80 views

Find the greatest common divisor of $8^{10}+12$ and $8^5$ without a calculator.

Find the greatest common divisor of $8^{10} + 12$ and $8^5$ I found the answer using a rather silly method: I found the GCD of the two numbers by finding the GCD of all the three numbers ...
-1
votes
1answer
49 views

Relations between the GCD of two numbers and the GCD of their linear combinations

(a) Prove that $a|b$ if and only if $\gcd(a,b) = a$. (b) Let $b > 9a$, Show that $\gcd(a,b) = \gcd(a,b−2a)$ (c) Show that If $a$ is even and $b$ is odd, then $\gcd(a,b) = \gcd(a/2,b)$ (d) Show ...
2
votes
1answer
84 views

Find sum of possible pairs for given LCM and GCD

I am given $A$ and $B$. I have to find out sum of $(m+n)$ for all pairs of numbers where $m\leq n$, $\gcd(m,n)=B$ and $\operatorname{lcm}(m,n)=A$ For $A=72$, $B=3$ Possible pairs will be - $(3,72)$, ...
0
votes
1answer
26 views

Can this simple divisibility property on binomial coefficient be proved without Gauss' lemma?

Consider the following property : ( * ) if $n\geq 1$, then $a_n=\binom{2n}{n}$ is divisible by $2n-1$. One can show that ( * ) is true as follows : $2n-1$ divides $na_n$ (because of the identity ...
0
votes
1answer
35 views

Find if there exist some combination of these digits that will be divisible by 8 or not

Let's say I am given some 100 digits and I have to find whether there can be any combination of these digits such that the number formed will be divisible by 8, how can I do that? I know divisibility ...
-2
votes
10answers
162 views

Show that the number $n$ is divisible by $7$ [duplicate]

How can I prove that $n = 8709120$ divisible by $7$? I have tried a couple methods, but I can't show that. Can somebody please help me?