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)

3
votes
3answers
233 views

A polynomial with integer coefficient

I'm struggling with this question: Suppose $P(x)$ is a polynomial with integer coefficients such that non of the values $P(1),...,P(2010)$ is divisible by $2010$. Prove that $P(n)\neq 0$ for all ...
3
votes
1answer
103 views

Find two elements that don't have a gcd in a subring of Gaussian integers

Find two elements in the domain $R := \{ x + 2y \sqrt {-1} \mid x,y \in \mathbb{Z} \}$ that do not have a gcd. I have no idea how to start. But I know if we consider $R^\prime = \{ x + y \sqrt ...
3
votes
6answers
211 views

Proof that $a^5 b - b^5 a$ is divisible by $30$ for any integers $a$ and $b$

I am trying to prove that $a^5\times b - b^5\times a$ is divisible by $3$. The actual task is to prove divisibility by $30$ but I have managed to prove that the expression is divisible by $5$ and $2$. ...
3
votes
1answer
200 views

GCD of Fibonacci-like recurrence relation

What is the greatest common denominator of $t(c^a)$ and $t(c^b)$, if $t(n) := k_1 f_1^n + k_2 f_2^n $? I already found out that the gcd is always a member of $t(n), n \in N $. $t(n)$ was originally ...
3
votes
1answer
83 views

Four fractions of certain factorials give another factorial

Let $n>0$ and $s_n=\sum_{k=1}^n k$. I looked at the expressions $\displaystyle\frac{s_n!}{(s_n-n)!}$ and found that the fraction is another factorial for $k=1,2,3,4$, i.e. ...
3
votes
1answer
1k views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
3
votes
2answers
338 views

Prove that every integer $n>0$ with $\gcd(n,10) = 1$ has a multiple that can be written with only the digit $9$. [duplicate]

Possible Duplicate: Proof that a natural number multiplied by some integer results in a number with only one and zero as digits The question is as stated. I'm really stumped on it. It seems ...
3
votes
2answers
307 views

Number of Divisor

How to find the Number of divisors of a number 'n' that are also divisible by another number 'k' without looping through all the divisors of n? I tried the following: Stored powers of all prime ...
2
votes
0answers
67 views

Find Gcd summation fast?

Find the value of the summation: $$ val=\left( \sum_{i=1}^a \sum_{j=1}^b\sum_{k=1}^c....\sum_{x=1}^p GCD(i,j,k,..x) \right)$$ Contraints $2\leq$number of summation terms$\leq 500$, $1\leq ...
2
votes
5answers
136 views

Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$

Could you help me with the problem below? Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$. Thank you!
1
vote
2answers
115 views

Let $d$ be a positive odd integer. Prove that there exists a positive $n \le d$ such that $d | 2^n − 1$.

I'm stuck on this question from my textbook which doesn't even have a solution. Any ideas ?. Help would be much appreciated. $$ d\, \left\vert\right.\, \left(2^{n} − 1\right) $$
1
vote
3answers
137 views

Basic Modulo Question

I've been having trouble with this example while studying for my exams. Why is $$2023^{2297}\equiv 20 \pmod{3953}\;?$$ Thanks so much for any help I can get! The examples solves the answer by ...
0
votes
4answers
145 views

Prove that if a and b are integers, then there are unique integers q and r such that $a = bq + r$, $-|b|/2 < r \le |b|/2$ [closed]

Prove that if a and b are integers, then there are unique integers q and r such that $$a = bq + r,$$ with the restriction that$$-|b|/2 < r \le |b|/2$$
0
votes
1answer
93 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
0
votes
1answer
79 views

Prime divisibility in a prime square bandtwidth

I am seeking your support for proving (or fail) formally the following homework: Let $p_j\in\Bbb P$ a prime, then any $q\in\Bbb N$ within the interval $p_j<q<p_j^2$ is prime, if and only if ...
33
votes
4answers
1k views

How does the divisibility graphs work?

I came across this graphic method for checking divisibility by $7$. $\hskip1.5in$ Write down a number $n$. Start at the small white node at the bottom of the graph. For each digit $d$ in ...
20
votes
1answer
475 views

Is $\sum_{k=1}^{n} k^k / \sum_{k=1}^{n} k \in \mathbb{N}$ for some $n > 1$?

Let $ A = \sum_{k=1}^{n} k^k $ and $ B = \sum_{k=1}^{n} k$, where $n >1 $ is a positive integer. Is $A/B$ ever an integer?
21
votes
10answers
1k views

Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$. I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not ...
4
votes
1answer
233 views

Divisibility of $2^n - 1$ by $2^{m+n} - 3^m$.

For what values of $m,n$ natural, do $2^n - 1$ is divisible by $2^{m+n} - 3^m$? Thank you very much.
8
votes
2answers
2k views

Divisibility Rules for Bases other than $10$

I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is ...
6
votes
1answer
82 views

Bezouts Identity for prime powers

I have two prime powers $2^n$ and $5^n$ for some arbitrary $n$. Their gcd is $1$ but how do I get their integer linear combination which is $1$ in terms of $n$. In other words what will be the ...
3
votes
6answers
1k views

Trick to find multiples mentally

We all know how to recognize numbers that are multiple of $2, 3, 4, 5$ (and other). Some other divisors are a bit more difficult to spot. I am thinking about $7$. A few months ago, I heard a simple ...
17
votes
3answers
710 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
9
votes
3answers
231 views

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$ I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ...
3
votes
2answers
91 views

$\gcd(c^a + 1, c^b + 1)$ for even $a$ and $b$?

Following on this question, what is the Greatest Common Denominator of $c^a + 1$ and $c^b + 1$, where $a, b, c \in N$. I know that for odd a and b, we have $\gcd(c^a + 1, c^b + 1) = c^{\gcd(a, b)} + ...
3
votes
1answer
83 views

Prove that $x^4+x^3+x^2+x+1 \mid x^{4n}+x^{3n}+x^{2n}+x^n+1$

Problem: Prove that $x^4+x^3+x^2+x+1$ divides $x^{4n}+x^{3n}+x^{2n}+x^n+1$ for all positive $n$ that are not multiples of $5$. I'd like to get some pointers about how to solve this. No full ...
2
votes
4answers
173 views

law of divisibility on $37$

how to find and prove law of divisibility on $37$? Thanks in advance. Added:---- how to prove for$37$ that: Split off the last digit, multiply by 11, and subtract the product from the number that is ...
2
votes
2answers
375 views

If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$

How to prove that: If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$ This statement is generalization of the statement from my previous question. I have checked for many $(a,b)$ ...
1
vote
5answers
63 views

Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.

Form the assumption, we can say $b=ak$ ,$k$ integer, $a=bm$, $m$ integer. Intuitively, this conjecture makes sense. But I can't make further step.
0
votes
2answers
54 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
14
votes
6answers
974 views

Divisibility criteria of 24. Why is this?

I am currently familiar with the method of checking if a number is divisible by $2, 3, 4, 5, 6, 8, 9, 10, 11$. While Checking for divisibility for $24$ (online). I found out that the number has to ...
8
votes
7answers
1k views

Proof for divisibility by $7$

One very classic story about divisibility is something like this. A number is divisible by $2^n$ if the last $n$-digit of the number is divisible by $2^n$. A number is divisible by 3 (resp., by ...
4
votes
1answer
117 views

$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$ isn't divisible by 5

I have no idea Prove that for any $n$ natural number this sum $$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$ isn't divisible by $5$. $\begin{array}{l} \left( {1 + x} \right)^{2n + 1} - ...
4
votes
2answers
135 views

Proving $\gcd( m,n)$=1 [duplicate]

If $a$ and $b$ are co prime and $n$ is a prime, show that: $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factor unless $a+b$ is a multiple of $n$ Also enlighten me why $n$ has to be prime so that ...
4
votes
1answer
97 views

how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $

how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
4
votes
2answers
724 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
2
votes
3answers
86 views

For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$.

I am trying to prove the following statement: For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$. So far I have figured out that $n^4 = 8m$ or $n^4 = 8m + ...
2
votes
2answers
265 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
3answers
333 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
2
votes
3answers
547 views

16 digit numbers divisible by 17

I wanted to know about the $16$ digit numbers those are divisible by $17$ and when this $16$ digit number is broken in groups of $4$ those groups of four are also divisible by $17$ and a check to ...
1
vote
2answers
66 views

Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$

I'm trying to prove that all integer solutions $a > b \ge 0$ to the divisibility condition in the title, namely $$(a^2+b^2+1) \mid 2(2ab+1),$$ are given by ...
1
vote
1answer
84 views

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b;a^2+b^2)= 1$ or $2$.

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b,a^2+b^2)$ is always equal to either 1 or 2, where $\gcd$ is the greatest common divisor. I haven't really ever solved a problem like this ...
1
vote
2answers
366 views

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n [duplicate]

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n Hi everyone, for the proof to the above question, Can I assume that since $(a, b) = ...
1
vote
2answers
209 views

Rabin's test for polynomial irreducibility over $\mathbb{F}_2$

I know that $f(x) = x^{169}+x^2+1$ is a reducible polynomial over $\mathbb{F}_2$. I want to show this using Rabin's irreduciblity test. First, I then have to check if $f$ is a divisor of ...
0
votes
1answer
75 views

Have you seen this theorem before? (GCD divides, neccessary & sufficient condition)

Conjecture. Let $a,b, c\in \Bbb{Z}, b \neq 0$, The following conditions are equivalent: (1) $d = \gcd(a,b)$ divides c. (2) There's a polynomial in $f \in \Bbb{Z}[X,Y]$ with $c$ constant term, such ...
0
votes
0answers
33 views

The elegant expression in terms of gcd and lcm - algebra - (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to ...
0
votes
2answers
108 views

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then [duplicate]

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then ${\gcd(a+b,}\frac{a^p +b^p}{a+b}$$) = 1$ or $p$ Sorry about the duplicate In another answer, however, the sum $\sum\limits_{k=0}^{n-1} ...
0
votes
1answer
56 views

Greatest common divisor of $3$ numbers

Let $a,b, c$ belong to $\mathbb Z$ such that $(a,b,c) \neq (0,0,0)$. Define the [highest common factor] greatest common divisor ${\rm gcd}(a, b, c)$ to be the largest positive integer that divides $a, ...
0
votes
1answer
46 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
0
votes
1answer
61 views

What is the concept behind divisibility of large numbers that contain only the digit 1?

An example question I found in a text book is : The 300 digit number with all digits equal to 1 is : A) Divisible by neither 37 nor 101 B) divisible by 37 but not by 101 C) divisible by 101 but not ...