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

learn more… | top users | synonyms

0
votes
2answers
205 views

Compute largest integer power of $6$ that divides $73!$

I am looking to compute the largest integer power of $6$ that divides $73!$ If it was something smaller, like $6!$ or even $7!$, I could just use trial division on powers of $6$. However, $73!$ has ...
0
votes
2answers
34 views

Combining GCD and congruences

Let $a, b, m, k \in \Bbb Z$ such that $m\ge2$ and $k\not=0$. Let $d=\gcd(k,m)$. Prove that if $a\equiv b\pmod m$ and $k$ is a common divisor of $a$ and $b$, then ${\frac ak}\equiv {\frac bk}\pmod ...
2
votes
1answer
21 views

How do I prove that $R=\{(x,y) \in S \times S : x\text{ divides }y\}$ is antisymmetric?

$S=\{1, 2, 3,\ldots, 1000\}$ $R=\{(x,y) \in S \times S: x \mid y\}$ My attempt: Assume $xRy$ and $yRx$. Then $x=ym$ and $y=xn$ for $m$, $n$ in Natural numbers. -So $x=xxn..$ that gets me nowhere. ...
1
vote
1answer
25 views

Reverse a division

I'm working on a program and I'm starting to regret the way I've done this. I start with a user selected number between 0.2 and 24 (lets call it a) then divide 12 by that number (so 12/a = b). Is ...
0
votes
2answers
241 views

Greatest common divisor power of 6 that divides 73!

Can someone please help me with the following problem? Compute the largest integer power of 6 that divides 73!.
2
votes
3answers
65 views

Where did the sum-of-divisors function come from?

Doing a research project on a few number-theoretic functions, and I was curious, where does the sum-of-divisors function come from? Surely someone thought it up and made it a possibility. I'm talking ...
0
votes
2answers
168 views

Congruence class $[a]$ modulo $m$, $\gcd(x, m) = \gcd(a, m)$

I'm currently stumped on this question: Let $a$ and $m$ be integers such that $m\ge1$. Consider the congruence class of $a$, i.e., $[a]$ modulo $m$. Prove that: For all $x\in[a]$, ...
2
votes
1answer
55 views

Is my understanding right on the divisiblity rule?

For a given number and a divisor. If the prime factors of the divisor can divide a number,then can I say that the divisor will divide a number. For example - 786 divide by 21 If I break 21 in the ...
0
votes
1answer
15 views

finding A using with restriction $1 \leq a \leq 20$ in GCD

For what $1 \leq a \leq 20$ you are finding $a$ is it true that $a^m+a^n=x^2$ for positive integers $a,m,n,x.$ I did $a^m+a^n=x^2.$ $=a^m(a^{n-m}+1)=x^2$ We know that since $(a,b)=1$ since the ...
7
votes
1answer
70 views

Prove or disprove $\gcd(q,r) \mid b$ if $a = bq + r$

Prove or disprove $\gcd(q,r) \mid b$ if $a, b, q, r \in \Bbb{Z}^+ \ni a = bq +r$ I'm pretty sure it's true (I can't think of a counter example), but I don't see how to prove it. Some of my ...
3
votes
2answers
82 views

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\dots+\frac{1}{1331}=\frac{p}{q}$; is $p$ divisible by $1997$?

if $p,q\in \mathbb{N}$ and $$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\dots+\frac{1}{1331}=\frac{p}{q}$$ why is $p$ divisible by $1997$?
0
votes
2answers
80 views

Compute remainder of division

I am trying to compute the remainder of the following division: $$9^{123456789} \quad\textrm{by}\quad 17.$$ Any ideas on how to work this out?
3
votes
1answer
58 views

Number of pairs $(A,B)$ with $\gcd(A,B)=B, A \ne B^2$ with $A,B \le n$

How many pairs $(A,B)$ of integers up to $n$ are there such that $\gcd(A,B)=B$, not counting those pairs where $B^2=A$? If we consider $n = 5$ we have $25$ possible pairs. They are ...
3
votes
2answers
191 views

Prove the $n$th Fibonacci number is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$

Prove that the $n$th Fibonacci number $f_n$ is the integer that is closest to the number $$\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n.$$ Hi everyone, I don't really understand the ...
3
votes
6answers
177 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
0
votes
0answers
60 views

Proof for $\gcd(F_m,F_n)=F_{\gcd(n,m)}$ [duplicate]

I saw many questions/answers, where: $$\gcd(F_m,F_n)=F_{\gcd(n,m)}$$ is taken as a fact. But how can I actually prove that this is true?
1
vote
1answer
85 views

Proving congruence class

Let $a$ and $m$ be integers such that $m ≥ 1$. Consider the congruence class of $a$, $[a]$ modulo $m$. It follows that $∀ x ∈ [a], \gcd(x, m) = \gcd(a, m)$. I have my algebra midterm in two ...
1
vote
1answer
60 views

Proving property of congruence - help needed

Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} ...
1
vote
7answers
93 views

Prove that $gcd(a, b) = gcd(b, a-b)$

I can understand the concept that $\gcd(a, b) = \gcd(b, r)$, where $a = bq + r$, which is grounded from the fact that $\gcd(a, b) = \gcd(b, a-b)$, but I have no intuition for the latter.
4
votes
2answers
58 views

If for all $n\in\Bbb{N}, a^n-n$ divides $b^n-n$ then $a=b$.

Exercise: Let $a,b\in\Bbb{N}$, show that if for all $n\in\Bbb{N}, \quad a^n-n$ divides $b^n-n$, then $a=b$. I don't have lot of knowledge on this subject, I am aware about some elementary result ...
2
votes
2answers
99 views

How can I prove that the square root of two prime numbers multiplied is non-rational number?

$P$ and $Q$ are two distinct prime numbers. How can I prove that $\sqrt{PQ}$ is an irrational number?
0
votes
2answers
64 views

Find all natural numbers n for which $3^n + 5^n$ is divisible by $3^{n-1} + 5^{n-1}$

Find all natural numbers n for which $3^n + 5^n$ is divisible by $3^{n-1} + 5^{n-1}$. Interested if there is a nice quick way other than mine.
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
votes
1answer
30 views

Set of a summation

Let $S = \{n ∈ N | n \text{ divides the sum of any n consecutive numbers} \}$. How can I describe the set S? I was given the hint: $\displaystyle\sum\limits_{n=1}^N n=\frac{N(N+1)}{2}$ I don't want ...
0
votes
1answer
69 views

Greatest Common Divisor of two binary polynomials

How can I find the GCD of $x^4 + x^3 + x^2 + 1$ and $x^6 + x^5 + x^4 + x^3 + x^2 + 1$? I know that $x^4 + x^3 + x^2 + 1$ is an irreducible polynomial of degree $4$, and that it is not primitive, but ...
4
votes
2answers
73 views

If $(a^2+b^2) \mid (c^2+d^2)$ and $\gcd(a,b)=\gcd(c,d)=1$ and $\gcd(a,c)>1$, what can be said about the components?

While working on a divisibility problem in integers $a,b,c,d$, with $\gcd(a,b)=\gcd(c,d)=1$, I've come up against the hypothetical condition $$ (a^2+b^2) \mid (c^2+d^2), \tag{$\star$} $$ where, also ...
0
votes
2answers
34 views

For any integer a, if $6|(3−a)$, then $3| (a−2)$. [closed]

Prove: For any integer a, if $6|(3−a)$, then $3| (a−2)$. I've been trying to work this problem for a while, but missed a day of class and can't seem to work it out.
2
votes
3answers
33 views

Prove if a|c and b|d and gcd(c,d)=1 then gcd(a,b)=1

I'm trying to prove that if a|c and b|d and gcd(c,d)=1 then gcd(a,b)=1 So far, I have assumed that: Since gcd(c,d) = 1 then by EEA, gcd(c,d) = 1 = cx + dy for some x,y that are integers. And since ...
3
votes
2answers
138 views

Probability a product of $n$ randomly chosen numbers from 1-9 is divisible by 10.

I'm working on a problem where each number is chosen randomly from 1-9. Given $n$ numbers chosen in this manner, we multiply all of these together. I'm looking for the probability that this product is ...
1
vote
1answer
25 views

if $p=(a+ib)(c+id)$ and $p^2 = a^2 + b^2$ then $p\mid a$ & $p\mid b$

We're working on Gauss integers... p is an odd prime such that $p \not\equiv 1 \pmod 4$. We want to prove that if there is $(a,b,c,d) \in \mathbb{Z}^4$ such that $$p = (a+ib)(c+id) \text{ ...
2
votes
0answers
29 views

Using divisibility and greatest common divisor for a proof [duplicate]

If u|t and v|t and gcd(u,v)=1, then prove that (uv)|t I started by analyzing the definition of divisibility and I got that (uv)|t^2, but this doesn't help me. Any advice would be appreciated. Thank ...
0
votes
1answer
46 views

If a|b and b|a, find the value of a in terms of b.

If a|b and b|a, where a and b are integers and a≠0, find the value of a in terms of b. Assume that b>0.
0
votes
1answer
68 views

Is it possible to find $n-1$ consecutive composite integers

Given an integer $n\geq 2$ ,can we always find an integer $m$ such that each of the $n-1$ consecutive integers $m+2,m+3,.....,m+n$ are composite?
2
votes
2answers
59 views

Which of the following numbers does not divide $2^{1650}-1$?

I'm practicing for a math competition that is coming up, and I got stuck on this question: Which of the following numbers does not divide $2^{1650}-1$? $3$, $7$, $31$, $127$, $2047$ I've seen a ...
1
vote
2answers
83 views

Algorithm to find the coefficient of GCD linear combination?

One of the properties of the GCD of two integers is that it can be written as the linear combination of the two, is there an algorithm that can be used to find the coefficients of this linear ...
2
votes
4answers
102 views

How to prove that $8^{18} - 1$ is divisible by $7$ [duplicate]

How to prove that: $$ 8^{18}-1\equiv0\pmod7 $$ In the simplest way?
0
votes
0answers
18 views

Proof with GCD(m, n) [duplicate]

How can I prove that equation below is true? If $a > b$ and $a, b$ are relatively prime numbers, then for $0 <= m < n$: $GCD(a^n - b^n, a^m - b^m) = a^{GCD(m,n)}-b^{GCD(m,n)}$
3
votes
0answers
39 views

GCD-Domain and proprieties

Let $A$ be a commutative GCD-domain (not necessary UFD or Bezout) and $a,b,c$ elements of $A$ such that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$. Is it true that $\gcd(ab,c) = 1$ ?
2
votes
1answer
63 views

The greatest common divisor is the smallest positive linear combination

How to prove the following theorems about gcd? Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$. ...
1
vote
1answer
36 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
1
vote
1answer
25 views

How can I show that the following number is not divisible by $p$ prime?

Let $p$ be a prime number. Let $k$ be some natural number and $r$ be some nonnegative integer. Then, I want to show that for $1\leq i\leq p^k-1$, \begin{equation*} \frac{p^{k+r}m-i}{p^k-i} ...
2
votes
3answers
52 views

How to prove that $\gcd(2n+3, 3n+1)$ divides $7$?

How can I start proving that gcd(2n+3, 3n+1) | 7? EDIT: It is $\gcd(2n+3, 3n+1)$ divides $7$. My bad. Thanks paw88789.
0
votes
3answers
53 views

Possible remainder when multiple of a number is divided by multiple of the same dividor

I have a couple of questions regarding which I am confused. $1)$ What is the Greatest, Positive Integer $n$ such that $2^n$ is a factor of $12^{10}$ $(3\cdot 2^2)^{10}$ So, my guess is $n = 12$? ...
0
votes
1answer
25 views

Find all $(h,k)$ such that $2^h \equiv 1 ~(\text{mod}~ 3^k) $

I'm facing with the following problem: Find all $(h,k)$ such that $$2^h \equiv 1 ~(\text{mod}~ 3^k) ~~~~~~~~(1)$$ and $$2^h \geq 3^k+1 ~~~~~~~~(2).$$ I'm just able to prove that the $(1)$ holds ...
0
votes
1answer
104 views

Product of roots of unity

Does somebody have a nice proof of the following? $$\prod_{m=1}^{n-1} \frac{e^{2\pi i k m/n} - 1}{e^{2 \pi i m / n} - 1} = \begin{cases} 1 & \text{ if $\gcd(k, n) = 1$} \\ 0 & ...
0
votes
1answer
29 views

Determine whether or not a binary number is divisible by $3$

Let $K$ be a natural number with $n$ binary digits. Is there an $O(n)$ method for deciding whether or not $K$ is divisible by $3$? $3|K \iff d_1-d_2+d_3-d_4\dots\pm d_n=0$ works correctly up to ...
0
votes
1answer
36 views

Primitive polynomial and divisibility

Let $f(x) \in \mathbb Z[x]$ with $c(f)=1$ and $f$ is non-constant. Now suppose $h(x) \in\mathbb Z[x]$ be such that $h(x)=f(x)q(x)$ where $q(x) \in\mathbb Q[x]$. Then I have to show that $q(x) ...
2
votes
3answers
104 views

$\dfrac1a+\dfrac1b=\dfrac1c$, $a, b, c \in \mathbb{N}$ with no common factor, find all solutions [duplicate]

Given $\dfrac1a+\dfrac1b=\dfrac1c$, where $a, b, c \in \mathbb{N}$ with no common factor, find all solutions. Actually, you can think this question as a follow up of this one. Today, I saw this ...
2
votes
1answer
249 views

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

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
1
vote
1answer
93 views

Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...