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
27 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
51 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 ...
1
vote
0answers
41 views

Greatest common divisor / euclidean algorithm linear combination proof [duplicate]

Consider integers $m$ and $n$, not both 0. Show that gcd$(m,n)$ is the smallest positive integer that can be written as $am + bn$ for integers $a$ and $b$. I'm confused on what exactly to do--I'm ...
3
votes
2answers
93 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 ...
2
votes
1answer
64 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 ...
1
vote
1answer
62 views

Use division algorithm to prove for any odd integer n, $n^2 -1$ is a multiple of 8.

Here is what I know if n is any odd integer then $n$ can be expressed as $n=2k+1 ~~~ where~k\in\mathbb{Z}$.So $n^2-1=(2k+1)^2 -1=4k^2+4k=4k(k+1)$ but $k(k+1)~~ is~~even$. Thus $k(k+1)=2t, t\in ...
2
votes
2answers
93 views

Factoring numbers of the form $11111111$

Why $11111111$ is divisible by $73$? How can we get all the prime factors? It is clear that it is divisible by $11$. Is there any formulae for $1111...11$ ($n$ times)? Give me some idea. Thanks in ...
1
vote
4answers
66 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 ...
1
vote
1answer
52 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
89 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
55 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$ ...
0
votes
0answers
13 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
64 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
38 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
28 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
vote
5answers
48 views

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$.

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$. I was able to go from left to right. But I'm having a hard time ...
-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
83 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
29 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
80 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
82 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
67 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
57 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
26 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
16 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
165 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
35 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
42 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
258 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 ...
-2
votes
2answers
165 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!$ 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
30 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
17 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
23 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
219 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
55 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
130 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
53 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
14 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
63 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
79 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
77 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
70 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
39 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
68 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
50 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
83 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
53 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
70 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?