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
28 views

$c=\text{gcd}(a,b)$ means $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show $\text{gcd}(x,y)=1$

Obvious homework question, so hints please: Suppose $a,b \in{\mathbb{Z}_+}$ and $c=\text{gcd}(a,b)$. So we know $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show that ...
0
votes
3answers
52 views

Prove that $\gcd(ab,m)\mid\gcd(a,m)\gcd(b,m)$ [closed]

Prove that if $a,b,m\in\mathbb N\setminus\{0\}$, then $$\gcd(ab,m)\mid\gcd(a,m)\cdot\gcd(b,m)$$
2
votes
0answers
24 views

How do I know the cyclic subgroups of G generated by a are equal?

I had a question of understanding that I was hoping you guys could help me with. Suppose there exists a group in the integers. For the sake of my understanding, let's say the group is, G = $Z_{60}$. ...
1
vote
4answers
56 views

Prove that if $a$ divides $ b$ , and $a$ divides $b + 2$ then $a = 1$ or $ a = 2$.

For positive integers $a,b$, prove that if $a$ divides $b$ and $a$ divides $b + 2$ then $a = 1$ or $a = 2$. I know that if $a|b$ and $a|c$ then $a|b+c$ or $a|b-c$ but I can't figure out how to get ...
2
votes
1answer
83 views

Prove that $\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a,b)} - 1$ [duplicate]

I have two questions about a prove that I have to do for my mathematic study. I'm now thinking about it the whole day, but can't find the prove. Let $a,b \in \mathbb Z_{>0}$. (a) Prove: ...
0
votes
1answer
28 views

Number theory,GCD, coprime integers

I am sorry for the bad title but I really can't think of a better one. So I was learning about the euclidean algorithm and I see a statement that is hard for me to understand. In the book that I was ...
1
vote
1answer
118 views

How to find the number of divisors that are perfect squares and divisible by a number

Suppose $ n = 2^{14} 3^{9} 5^{8} 7^{10} 11^{3} 13^{5} 37^{10} $ , find the number of positive divisors that are both perfect squares and divisible by $ 2^{2}3^{4}5^{2}11^{2}$. It is quite simple to ...
1
vote
0answers
44 views

If p is a prime what values of $ a\leq p^{n}$ have $\text{gcd}(a, p^{n}) >1$?

Hi guys need your help. Sorry but I don't understand how to use latex. So really sorry for the writing. The question is if p is prime what values of $ a\leq p^{n}$ have $\text{gcd}(a, p^{n}) >1$? ...
0
votes
0answers
18 views

synthetic division for find function answer reasoning

Why use synthetic division to find, say f(5), when you could just plug in 5 in place of all the x in the function and solve directly? Is there something more to this? Do some people just find it ...
0
votes
1answer
55 views

Proof that $\operatorname{lcm}(a, b) = ab / \gcd(a,b)$ and $\gcd(a,b) \le |a - b|$ for $a \ne b$

What's the simplest proof that the least common divisor of $a$ and $b$ is equal to the product of $a$ and $b$ divided by the greatest common divisor, i.e.: ...
1
vote
3answers
45 views

Strategy for solving $7\vert2^{n+2}+3^{2n+1}$ by induction.

So I have to show the following to be true using induction $7\mid 2^{n+2}+3^{2n+1}$ This is easily checked with the case $n=0$ because $7 \mid 7$, but I assuming this holds for$n=k :$ $$7\mid ...
2
votes
2answers
33 views

Proof by Induction: for all integers n $\ge$ 0, $12\mid8^{2n+1}+2^{4n+2}$

I'm working on a homework problem for my discrete math class, and I'm stuck. (Note: I made a post about this earlier, but I read the problem incorrectly, thus the work was wrong, so I deleted the ...
4
votes
1answer
30 views

Is there an $n$ such that $p|n^2+1$ with $2n<p<2n+\sqrt n$?

Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$? It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible ...
0
votes
2answers
30 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
1
vote
2answers
84 views

Divisibility problem using DFA

Original problem: Create a DFA for every positive integer $k$, so that when DFA takes a binary string (reading from most significant bit), decides whether the number is divisible by $k$. A DFA for a ...
0
votes
2answers
57 views

Proving a polynomial is not divisible

Let $k\geq2$ be even and let $f(x)=x^{k}+x^{k-1}+...+1\in\mathbb{Q}[x]$ I want to prove that there is no linear polynomial that divides $f(x)$ So I figured that if there was $g(x)=x-\alpha$ that ...
5
votes
3answers
46 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 ...
0
votes
2answers
55 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
35 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 ...
2
votes
3answers
64 views

Proof that if $\gcd(a,b) = 1$ and $a\mid n$ and $b\mid n$, $ab \mid n$

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 ...
1
vote
1answer
143 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
99 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 ...
5
votes
3answers
117 views

prove that $2^n+2^{n-1}+2^{n-2}+8^n-8^{n-2}$ is a multiple of 7

Prove that a number $2^n+2^{n-1}+2^{n-2}+8^n-8^{n-2}$ is a multiple of 7 for every natural $n\ge2$. I am not sure how to start.
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
59 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
109 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 ...
3
votes
1answer
66 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
90 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
97 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
69 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
55 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
101 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
56 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$ ...
2
votes
5answers
93 views

Prove that if $3\mid n^2 $ then $3\mid n $. [duplicate]

$n \in \mathbb{N}$ Prove that if $3\mid n^2 $ then $3\mid n $ I want to prove this in a accepted formal way, I thought about the fact that every integer can be written as multiplication of prime ...
0
votes
2answers
84 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
40 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
50 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 ...
3
votes
1answer
27 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
85 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
36 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
87 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
73 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
62 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
27 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
18 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
168 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 ...