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)

0
votes
2answers
54 views

Using inclusion-exclusion principle to count the integers in $\{1, 2, 3, \dots , 100\}$ that are not divisible by $2$, $3$ or $5$

Question: How many integers in $\{1, 2, 3, \dots , 100\}$ are not divisible by $2$, $3$ or $5$? Can anyone give me a full explain of how this applies to the inclusion-exclusin principle? Because I ...
0
votes
1answer
37 views

Dividing a number into infinite pieces

Last day in physics teacher said that any number divided into infinitely many pieces is zero.It got me thinking in kind of weird direction so here is what I was thinking about and how I tried to ...
1
vote
1answer
26 views

Proving that $\varphi(n)$ is divisible by $\varphi(n_1)$ and $\varphi(n_2)$

So, I've been thinking about trying to prove this statement - If $n=n_1n_2$ and $n_1$ and $n_2$ are relatively prime integers greater than 2, prove both $φ(n_1)$ and $φ(n_2)$ divide $φ(n)$. In ...
4
votes
3answers
51 views

divisibility of $n^{15} - n^3$ by $32760$

I have a question & I have no idea where to begin. I hope someone here can help me. Been stuck for a while. Prove or disprove: $n^{15} - n^3$ is divisible by $32760$ for all $n \ge 0$.
-1
votes
4answers
47 views

When $a$, $b$, and $c$ are positive integers, we have $\gcd{(a, b)}=\gcd{(a+cb, b)}$? [closed]

When $a$, $b$, and $c$ are positive integers, I want the proof for $\gcd{(a, b)}=\gcd{(a+cb, b)}$. Thanks in advance.
3
votes
1answer
26 views

Game picking cards so that sum is divisible by $25$

Adele and Bryce play a game. There are $50$ cards, numbered $1,2,\ldots,50$. They take turns alternately picking a card, with Adele going first. If at the end, the sum of the numbers on Adele's cards ...
5
votes
1answer
81 views

Does the A001921 linear recurrent integer sequence always yield composite numbers?

Let $(a_n)$ be the A001921 sequence $$ a_0 := 0,\ a_1 := 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6. $$ Is it true that $a_n$ is always a composite integer for any $n\geq 2$ ? UPDATE : I now make a ...
0
votes
0answers
28 views

Use Euclidean algorithm to find the gcd

$$f(x)=x^3+3x^3+2x+4$$ $$g(x)=x^2+1$$ in $\mathbb Z/5 \mathbb Z[x] $ I got $f(x)=g(x)(x^2+3x+1)+(5x+5)=g(x)(x^2+3x+1)$ as $5x+5->0$ in $\mathbb Z/5 \mathbb Z$, by long division I am not sure how ...
5
votes
2answers
79 views

Function with $f(a)-f(b)$ dividing $a^3-b^3$

What are all functions $f:\mathbb{Z}\rightarrow\mathbb{Z}$ such that $f(a)-f(b)$ divides $a^3-b^3$ for all $a,b\in\mathbb{Z}$ such that $f(a)\neq f(b)$? The constant functions satisfy vacuously, and ...
5
votes
1answer
78 views

Find $\gcd$ of two polynomials in $\mathbb{Z}_5[x]$

Question: Find $\gcd$ of $x^4+3x^3 +2x+4$ and $x^2-1$ in $\mathbb{Z}_5[x]$ Applying the Euclidean Algorithm as my book suggests, I got the following: $x^4+3x^3+2x+4=(x^2-1)(x^2+3x+1)+(5x+5)$ ...
5
votes
1answer
65 views

Maximum number dividing $\prod_{i<j}(a_i-a_j)$

Fix an integer $n$. What is the maximum number guaranteed to divide $\prod_{i<j}(a_i-a_j)$ for any integers $a_1,\ldots,a_n$? For instance, if $n=3$, then two of the three numbers have the same ...
1
vote
1answer
54 views

Coprime, commensurable integers

I really need help with proving this problem: For natural numbers k,n > 0 we define set M(k,n) = {k,2k,3k...nk}. Find out which elements are in following sets: a) M(i,n) intersection M(j,n), where ...
1
vote
2answers
24 views

Find the least $n$ such that the fraction is reducible

So I have this type of question I've never seen before. It smells like Number Theory to me, and I've never studied Number Theory, but I know a very few, very basic Number Theory facts. For instance ...
0
votes
0answers
12 views

Axiom of extensionality and Venn diagrams to derive GCD

This is mostly a question of what kind of language to use when explaining the following so as to be rigorous. The wikipedia article on GCD presents a nice intuitive Venn-diagram-based way to derive ...
7
votes
0answers
160 views

Does $A193201$ count the partitions of $n$ of arbitrary dimension?

By my count, these sequences match for $n=0\ldots6$, where partitions that are the same after relabeling dimensions are considered equivalent (i.e., the dimensions are unordered). For example, for ...
0
votes
1answer
32 views

Prove or disprove: (i) gcd(a,q) = gcd(q,r) (ii) gcd(q,r)|b (iii) gcd(b,r) = gcd(a,q) (iv) gcd(a,r)|q

Given a,b,q,r ∈ ℤ ∋ a = bq + r. Prove or disprove the following: (i) gcd(a,q) = gcd(q,r) (ii) gcd(q,r)|b (iii) gcd(b,r) = gcd(a,q) (iv) gcd(a,r)|q Part (i) is no problem. I'm getting hung up on part ...
1
vote
3answers
38 views

Proving a mod b < a/2 when a > b > 0

Suppose that $a \gt b \gt 0$. How can one prove that $a$ mod $b \lt a/2$? I understand why is that happening: if $a$ mod $b \gt a/2$ that means that $a/b \lt a/2$ and $a/b$ has enough "space" to ...
4
votes
3answers
249 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...
-3
votes
2answers
116 views

Compute largest integer power of $6$ that divides $73!$ [closed]

I am looking to compute the largest integer power of $6$ that divides $73!$ I need to show working out also. Any help or hints appreciated
0
votes
2answers
29 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
16 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
22 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
210 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
50 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
125 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
51 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
13 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
61 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
78 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
75 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?
1
vote
2answers
65 views

Use Fibonacci number to prove that is the integer that is closest to another number

Hi everyone, I don't really understand the problem. I have the following hint, but I don't know how to work it.
0
votes
0answers
34 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
63 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
45 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} ...
4
votes
2answers
50 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 ...
1
vote
2answers
52 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
61 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.
-1
votes
1answer
28 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
41 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
62 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
32 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
27 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 ...
2
votes
2answers
82 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
22 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{ ...
1
vote
0answers
22 views

Using divisibility and greatest common divisor for a proof

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
45 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
45 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?
1
vote
2answers
45 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
44 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 ...
3
votes
4answers
84 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?