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)

5
votes
3answers
44 views

Divisors $1\bmod 4$ more than $3\bmod 4$

For any positive integer $n$, let $f(n)$ denote the number of positive divisors of $n$ which are $1\bmod 4$, and $g(n)$ denote the number of positive divisors of $n$ which are $3\bmod 4$. Is it true ...
2
votes
0answers
19 views

Does this expression involving GCDs simplify?

I've run into a strange thing: $$\gcd\left((a^2+c^2)(b^2+c^2),4c \gcd\left( a(b^2 + c^2), b(a^2 + c^2), 2a b(a + b) \right) \right)$$ Given that $1 =\gcd(a,b,c)$, does the above complicated-looking ...
0
votes
2answers
36 views

Weak Mathematical Induction for Modulo Arithmetic

Using Weak Mathematical Induction, I have to show that, for all integers $n \geq 1$, $8|3^{2n} -1$ I really don't know how to go about solving this problem. Currently I only have the base case and ...
0
votes
1answer
27 views

Basic question on Number Theory and Divisibility

Prove or disprove that if $a\mid(sb + tc)$ for all $s,t$ elements of integers, then $a\mid b$ and $a\mid c$ My question is "for all". I'm clearly misunderstanding something, because my intuition is ...
1
vote
1answer
28 views

Proof with greatest common divisors

I'm learning about properties of greatest common divisors, specifically when two numbers are relatively prime. The exercise I'm working through is : Suppose that $\gcd(a,b) = 1$ and that $a\mid n$ ...
1
vote
1answer
137 views

question about cryptography

Sam and Tim have set up their RSA keys (eS; n); (eT; n), respectively, where the n-value is the same. Furthermore, it happens that gcd(eS;eT) = 1. Suppose that their friend Rob wants to send both Sam ...
5
votes
0answers
67 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 ...
0
votes
2answers
25 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
34 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 ...
0
votes
0answers
36 views

Greatest common divisor / euclidean algorithm linear combination proof

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
81 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
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 ...
1
vote
4answers
61 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
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, ...
-5
votes
3answers
52 views

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

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
4answers
84 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
47 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
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
41 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
35 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
25 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
50 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
46 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
25 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
79 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
27 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
78 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
48 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
158 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
244 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
109 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
28 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
204 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
48 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
116 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
50 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
77 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
60 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
32 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?