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
1answer
31 views

Divisiblity of $n$ with $a,b,c$ is relative prime to p

Given an arbitrary prime $p > 2011$. Prove that there exist positive integers $a,b,c$ such that there exists some numbers from $a, b, c$ that are relatively prime to $p$, and for all positive ...
0
votes
2answers
57 views

If $\gcd (x,4) = 2$ and $\gcd(y,4) = 2$ then $\gcd(x+y,4) = 4$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $(x, 4) = 2$ and $(y, 4) =2$, then $(x + y, 4) = 4$, where $(a,b)$ denotes the ...
0
votes
4answers
79 views

GCD : Why does the GCD of two numbers divides their difference?

I was working my way through some number theoretic proofs and being a newbie am stuck on this proof : Why does the gcd of two numbers , say (a,b) - also divides their difference : a-b My ...
11
votes
1answer
170 views

Are there infinitely many pairs of primes where one divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
0
votes
1answer
55 views

Highest common factors of polynomials

Let h be a hcf of $f, g \in K[x]$ Then there exists polynomials a and b such that $h = af + bg$ Can anyone explain this theorem to me intuitively?
4
votes
3answers
143 views

True or False: $2^{2^{2011}} \text{ divides } 2^{2^{2012} }$

True or false: $$2^{2^{2011}} \text{ divides } 2^{2^{2012} }$$ Give your justifications. I don't know how to start this problem so far. But, I guessed like this, $$2^{\underbrace{2\times ...
2
votes
4answers
132 views

Prove that $p$ divides $F_{p-1}+F_{p+1}-1$ [duplicate]

Given the Fibonacci sequence $(F_n)$, defined by $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$, and $p$ an odd prime number, how to prove that $p$ divides $F_{p-1}+F_{p+1}-1$? Is induction a good idea here? ...
0
votes
3answers
58 views

Help me answer this Number Theory question on GCD (involves exponents) [duplicate]

Basically I need a good hint how to solve the problem.I have solved it partly. $gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1$. I have reached till: $gcd(2^a-1,2^b-1)=gcd(2^{a-b}-1,2^b-1)$ How to ...
1
vote
3answers
69 views

If $\gcd (a,b) = 1$, what can be said about $\gcd (a+b,a-b)$?

Suppose $a, b \in \mathbb{Z}$, $a > b$, and $\gcd (a,b) = 1$. What can be said about $\gcd (a+b,a-b)$? Is it true in general that $\gcd (a+b,a-b) \leq 2$?
1
vote
1answer
49 views

To find all positive integers $n$ such that $n|a^2-1 ; a \in \mathbb Z \implies n|a-1 $ , or $n|a+1$

How do we find all positive integers $n$ such that $n|a^2-1 ; a \in \mathbb Z \implies n|a-1 $ , or $n|a+1$ ? I have found that for any odd prime $p$ and $n \in \mathbb Z^+$ , $p^n|a^2-1 ; a \in ...
1
vote
0answers
43 views

Proving the Divisibility Rule for $3$ [duplicate]

Theorem: If 3 divides the sum of the digits of a number, then 3 divides that number
1
vote
2answers
55 views

For every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$.

Use induction to prove that for every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$. I can see that for $n=1$, $ 3^{3} -1=26\cdot 1$. As for inductive step, assuming that the statement ...
3
votes
1answer
401 views

Significance of GCD

I understand GCD mathematically but i can't figure out where to apply it. For eg I saw this problem today: Adam is standing at point $(a,b)\in\mathbb Z^2$ in an infinite 2D grid. He wants to ...
1
vote
2answers
84 views

12 column grid, how to calculate for columns(5,7,8,9,10,11)?

I am terrible at math, this is css/sass related, but it's mainly a math question. I feel like the answer is very easy. You can see for example col-1 is ...
2
votes
1answer
120 views

Algebraic number theory exercise

I'm trying to do the following exercise from Neukirch's Algebraic Number Theory (exercise 2, $\S 1$, chapter 1): Show that, in the ring $\mathbb{Z}[i]$, the relation ...
-1
votes
1answer
90 views

probability divisible by 11 [closed]

$S$ is a set of the natural numbers with $10$ digit which each of the digits is different such $2901843756$. If a number is choosen fron set $S$ then the probability the number is divisible by $11$ ...
1
vote
2answers
86 views

Converting Decimal to Hexadecimal

MathExchange, I am trying to learn more about computers, and one thing I have opted to teach myself is decimal to binary, and decimal to hex conversion. From the web, I have found tutorials on ...
0
votes
0answers
35 views

Does this notation mean what I intend?

I was looking at divisibility rules earlier today and noticed that several of them had the same form, i.e. truncating the last digit and then adding or subtracting a multiple of it to the truncation. ...
7
votes
2answers
124 views

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$.

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$. so I put $n=2k$ and I supposed $n \mid 1^n +2^n+3^n + \ldots (n-1)^n$ then with a little calculation we ...
0
votes
1answer
43 views

To find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$

How do we find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$ ? The primes certainly satisfy this condition ; what other integers do satisfy this condition ...
0
votes
1answer
42 views

For odd $n$, there is an $m$ such that $n \mid 2^m-1$

I am really stuck with this question: Suppose $n$ is an odd positive integer. Prove that there exists a positive integer $m$ such that (2^m − 1)\n . (Here, “divides” means that when 2^m − 1 is ...
1
vote
2answers
88 views

Divisibility of $987x^n − F_nx^{16} + F_{n−16}$

If $F_n$ is $n^{th}$ Fibonacci number, and polynomials $P_n(x)$ are defined as $987x^n − F_nx^{16} + F_{n−16}$, prove that for all $n ≥ 1$, $P_n(x)$ is divisible by $x^2−x−1$. This is from a ...
1
vote
1answer
17 views

Average Speed Calculation

An airplane leaves New York at 1:10 PM and arrives in Miami, 1125 miles away, at 3:40 PM. What is its average speed in miles per hour? Isn't the formula speed = distance/time? It didn't work for me ...
3
votes
1answer
211 views

How many positive integers less than 1000 are multiples of 5 and are equal to 3 times an even number?

Question: How many positive integers less than 1000 are multiples of 5 and are equal to 3 times an even number? So Multiples of $5$ and $6$ If a number is a multiple of $5$ and $6$ then it is a ...
3
votes
4answers
114 views

$2^{2^n}+5^{2^n}+7^{2^n}$ is always divisible by $39$

This problem is really bothering me for some time, I appreciate if you have some idea and insight. Prove that $$2^{2^n}+5^{2^n}+7^{2^n}$$ is divisible by $39$ for all natural numbers ...
2
votes
1answer
66 views

Does $a\in\mathbb Z$ such that $\gcd(n,a(m-a))=1$ exist for every $(m,n)\not=(\text{odd},\text{even})$?

When I was thinking about the greatest common divisors, I noticed that we seem to be able to find at least one integer $a$ such that $$\gcd(n,a(m-a))=1$$ for every pair of positive integers $(m,n)$ ...
4
votes
1answer
300 views

Comparing two definitions of a set of natural numbers

Let $n_1,n_2,N\in \mathbb{N}$. I want to show the following: The two sets \begin{align*} &\Delta(n_1,n_2,N)\\ =& \Big\{ a\cdot b: \quad a\mid {n_1}^2,~a^2 \mid {n_1}^2N ,\gcd\left(N ...
4
votes
2answers
70 views

GCD in Gaussian integers.

If you have two different common divisors in an integral domain that is not a multiple of each other, is the gcd then equal to the divisor that has the largest norm?
3
votes
1answer
61 views

For every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$. I have no idea how to prove that.
36
votes
5answers
6k views

If a prime number is reversed, and then appended to itself, why is the result always a composite number?

$2 \Rightarrow 22$ which is a composite number. $37 \Rightarrow 3773$ which is a composite number. $523 \Rightarrow 523325$ which is a composite number. $8123 \Rightarrow 81233218$ which is a ...
4
votes
0answers
111 views

Reducing multivariate rational fractions to lowest terms

I wish to simplify multivariate rational fractions to a canonical form. Thanks to some very helpful mathematically inclined people who verified that my understanding of Wikipedia was correct, I'm now ...
-2
votes
0answers
158 views

Prove that $n^4−1 $ is divisible by 5 when n is not divisible by 5. [duplicate]

Apparently the easiest method is to use proof by exhaustion, but I've no idea how. Any ideas/solutions? Prove that $n^4−1$ is divisible by 5 when n is not divisible by 5.
1
vote
1answer
29 views

Divisibility lemma: $\exists n_0\mid n,\,\, m_0\mid m,\,(n_0,m_0) = 1,\text{ and }\,[n_0,m_0] = [n,m]$

I want to prove that, in a commutative group, there always exists an element whose order is $\mathrm{lcm}$ of the orders of two other elements. The exercise indicates that it follows easily from the ...
-1
votes
1answer
421 views

Count permutations with LCM

Given $N,M$ and $D$ we need to count how many permutations of $N$ integers are there with each $i$'th element $1 \le A[i] \le M$ such that least common multiple (LCM) of all its elements is divisible ...
3
votes
4answers
78 views

Proof of divisibility using modular arithmetic: $5\mid 6^n - 5n + 4$

Prove that: $$6^n - 5n + 4 \space \text{is divisible by 5 for} \space n\ge1$$ Using Modular arithmetic. Please do not refer to other SE questions, there was one already posted but it was using ...
3
votes
1answer
55 views

Deceptively simple divisibility problem

Suppose we are given integers $a,b$ with the condition that there exists a prime $k$ such that $$2a+b\mid (a+b)^k$$ What can we say about $\gcd(a,b)$? So far, I can see that for all primes $p:p\mid ...
0
votes
1answer
47 views

Confusion (Divisible, Multiples)

So the question is "How many numbers between $3$ and $101$ are exactly divisible by $4$?" I found out that the answer is $25$. When reading this question over, a thought came into my head. What if ...
-1
votes
1answer
482 views

Finding $GCD$ excluding some elements from an $array$ [closed]

I have an array of numbers. I want to calculate $GCD$ of all numbers but excluding numbers from particular index $a$ to index $b$. I need to repeat the same operation multiple times with different ...
2
votes
2answers
90 views

Proving $310 \mid n^{121}-n$ for all integers $n$

I wrote it as $n^{120}=1\pmod{310}$ and thought I'd divide it in simpler congruences with primes (is this right?) $$n^{120}=n^{4\cdot30}=1\pmod{31}$$ $$n^{120}=n^{30\cdot4}=1\pmod{5}$$ But then I'm ...
9
votes
9answers
296 views

What is $\underbrace{555\cdots555}_{1000\ \text{times}} \ \text{mod} \ 7$ without a calculator

It can be calculated that $\frac{555555}{7} = 79365$. What is the remainder of the number $5555\dots5555$ with a thousand $5$'s, when divided by $7$? I did the following: $$\begin{array} & ...
5
votes
1answer
178 views

Prove Divisibility In Fibonacci Sequence Over A Prime Number

In The Fibonacci sequence which is defined as: Lets say we have the number $p$ which is an odd prime. Prove that: $F_{p-1} + F_{p+1} -1$ Is divisible by $p$. Prove that for any given $n$ real ...
3
votes
1answer
29 views

Are there positive integers $x, y$ and $z$ such that $2^{x} · 3^{4} · 14^{y} = 126^{z}$

Can anyone give me a tip on how to approach this. Possibly a theorem of some sort that allows me to work with powers using modular arithmetic. Thanks for the help.
0
votes
0answers
29 views

If no elements of a sequence $a_n$ are divisible by $\pi$, does $\forall n, a_n \mod \pi \in (0;\pi)$ hold?

Given a sequence like $a_n = n$ or $a_n = 50n$, (or any arbitrary constant), and that no element of the sequence is divisbile by $\pi$, would $b_n = a_n \mod \pi$ eventually take on all values in the ...
1
vote
0answers
37 views

On integer $n>1$ and prime $p$ such that $p<n$ , $p$ does not divide $n$ and $n-p$ is a prime

Let $n>1$ be a given integer and $p$ be a prime less than $n$ and not dividing $n$ ; so $p$ and $n$ are co-prime ; hence $n-p$ and $n$ are also co-prime ; I would like to ask when is $n-p$ also is ...
1
vote
1answer
48 views

Hints for solving this Number Theory problem on divisibility

Find all positive integers $d$ such that $d$ divides both $n^{2}+1$ and $(n + 1)^{2}+1$ for some integer $n$. Currently what I am thinking of is like manipulating $n^{2}+1$ and finding out the ...
3
votes
3answers
76 views

Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$

Find the greatest common divisor of $2003^4 + 1$ and $2003^3 + 1$ without the use of a calculator. It is clear that $2003^4+1$ has a $082$ at the end of its number so $2003^4+1$ only has one factor of ...
2
votes
3answers
138 views

Divisibility test by 7

Pohlmann-Mass method Step A: If the integer is 1,000 or less, subtract twice the last digit from the number formed by the remaining digits. If the result is a multiple of seven, then so is the ...
6
votes
1answer
80 views

How does the size of the set $A(R) = \{(a,b) \; | \; a,b \in N \times N, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$ grow?

How does the size of the set $$A(R) = \{(a,b) \; | \; a,b \in \mathbb{N} \times \mathbb{N}, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$$ grow as a function of $R$? My try: It's clear that $|A(R)| ...
2
votes
1answer
49 views

Question regarding gcd in polynomial ring over a field

Let $\mathbb{F}_q$ be a finite field. We have a polynomial ring $\mathbb{F}_q[t]$ and its field of fractions, which we denote $\mathbb{K}$. Suppose I have polynomials $f_1, \ldots, f_n$ in ...
2
votes
1answer
92 views

On a proof that “there are at least $F_n$ Collatz permutations of length $n$”.

Let $n, k \in \Bbb{N}$ and $F_n$ be the $n$th term of the Fibonacci sequence. Let $u$ be the map $x \to 3x+1$ and $d$ be the map $x \to \frac{x}{2}$. Let a type be a sequence of $u$'s and $d$'s. ...