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)

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 ...
5
votes
0answers
74 views

Product of consecutive Fibonacci numbers divisibility

Prove that the product of any $k$ consecutive Fibonacci numbers is divisible by the product of the first $k$ Fibonacci numbers. We can try to show that for every prime $p$, the power of $p$ appearing ...
2
votes
1answer
60 views

Statement about divisibility

Let's consider such function: $$f(N) = 1^1\cdot 2^2\cdot 3^3 \dots (N-1)^{N-1}\cdot N^N.$$ Does the expression $$\frac{f(N)}{f(r)\cdot f(N-r)}$$ is always integer? Can you give me any hint about ...
0
votes
2answers
26 views

divisibility relation $a|b^2 + 10c.$

Use divisibility relation to show that for all integer $a$, $b$, $c$, $a \ne 0$ counts if $a|b$ and $a|c$ then $a|b^2 + 10c$. Use direct proof. Ok, $a|6$ then there is integer $k$. $$a*k=6,$$ ...
1
vote
3answers
44 views

Mathematical Induction divisibility

So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ , $$ 8|(3^{2n} - 1)$$ (is divisible by 8) I have my base case: [P(1)], $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the ...
3
votes
2answers
86 views

Prime elements in the gaussian integers

Prove: If a prime number $p\in \mathbb N$ is from the form $p=4k+3,k\in \mathbb N$, then its also a prime number in $\mathbb Z[i]$,i.e. if $p|(z_1\cdot z_2)$ then $p|z_1$ or $p|z_2$. I dont have any ...
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 ...
-5
votes
3answers
64 views

How many numbers less than 10000 are there which are divisible by 21, 35, 63? [closed]

I am trying to determine: How many numbers less than $10000$ are there which are divisible by $21$, $35$, $63$? To be clear, let me add that I want numbers that are divisible by each of $21$, ...
1
vote
1answer
50 views

The number $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$.

Prove that for every $n\in \mathbb N$, $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$. I was able to prove that $2^{3^n}+1$ is divisible by $3^{n+1}$ using induction. First, ...
1
vote
4answers
62 views

How am I supposed to tell if a number is divisible by $13$ (I need a shortcut)?

I've been trying to figure out if a number is divisible by $13$. As I'm saying this in first person, I think I'm supposed to take the rightmost digit of the number, for example, $39$, multiply it by ...
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 ...
1
vote
4answers
87 views

Show that $(k!)^n$ divides $(kn)!$

Show that $(k!)^n$ divides $(kn)!$ I've tried it but without success. Any help would be great.
1
vote
2answers
49 views

Prove that, given positive integers m and n, if m | n then 2^m − 1 | 2^n − 1. In particular, deduce that if 2^n − 1 is prime then n is prime.

I think I have the first part of the proof down but I would like to double check that my logic works: m|n $\Leftrightarrow$ n = k*m $\Rightarrow$ $2^n-1 = 2^{km}-1$ ...
5
votes
7answers
5k views

If gcd (a,b)=1 and gcd (a,c)=1, then gcd (a,bc)=1

How do I go about proving this? If gcd (a,b)=1 and gcd (a,c)=1, then gcd (a,bc)=1. I'm very confused with gcd proofs.
0
votes
1answer
63 views

Under what conditions can $a\sqrt{b} \pm c\sqrt{d}$ be written as $u+v\sqrt{w}$?

Let $a,b,c,d \ge 1$ be integers with $b$ and $d$ nonsquare and $a\sqrt{b} \ge c\sqrt{d}$. Now I have three related questions: Under what conditions can one find $u,v,w$ such that $a\sqrt{b} \pm ...
0
votes
0answers
12 views

Which integer linear recurrent sequences are divisibility sequences?

The Lucas sequences are very remarkable because they are integer linear recurrent sequences and divisibility sequences at the same time. Are other examples known ? Is there a characterization of such ...
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 ...
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 ...
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 ...
-11
votes
0answers
297 views

Is the factorial of the sum of three integers divisible by the product of their factorials? [closed]

Since binomial coefficients are integers, we know that $(x+y)!$ is divisible by $x!y!$ for every nonnegative integers $x,y$. Is it also true that $(x+y+z)!$ is divisible by $x!y!z!$? If so, how to ...
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 ...
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 ...
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)$ ...
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
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 ...
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 ...
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 ...
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 ...
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!.
-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
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]$, ...
-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 ...
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 ...
11
votes
2answers
653 views

What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?

What is the remainder when $$1! + 2! + 3! +\cdots+ 1000!$$ is divided by $12$. I have tried to find the answer using the Binomial Theorem but that doesn't help. How will we do this? Please help.
5
votes
2answers
102 views

If $a^n-1$ is divisible by $b^n-1$ for all $n$, then $a$ is a power of $b$

Let $a,b$ be natural numbers not equal to $1$ such that $\frac{a^n-1}{b^n-1}$ is natural for any natural $n$. Prove that $a=b^m$ for some natural $m$.
2
votes
1answer
32 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$. ...
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 ...
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?
2
votes
3answers
72 views

Divisibility by primes

Suppose that $n$ is a natural number, $n \ge 2$, and $n$ satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide n. If $p$ is prime, $p$ divides $n$ if and only if $(p − 1)$ divides $n$. ...
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.