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
0answers
11 views

What can we say about $\frac{s}{p}$, $\frac{p}{s}$ using these 3 imposed conditions?

What can we say (if anything) about $\frac{s}{p}$ or $\frac{p}{s}$ where $p$ and $s$ are integers greater than $1$ using the following three conditions: $p>s$, $s$ and $p$ are not both divisible ...
1
vote
2answers
17 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
83 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
70 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
35 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
33 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
3answers
118 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
42 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
37 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
83 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
16 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
59 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
99 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
58 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
293 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 ...
1
vote
2answers
39 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
58 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.
34
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
59 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
151 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
23 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 ...
0
votes
1answer
373 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
64 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
53 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
40 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 ...
0
votes
0answers
440 views

Finding $GCD$ excluding some elements from an $array$

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
85 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
274 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} & ...
0
votes
4answers
86 views

What is the greatest positive three digit integer that is divisible by 5, 7 and 9? [closed]

Finding the greatest positive three integer divisible by $5$, $7$ and $9$.
5
votes
1answer
112 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
28 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
26 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
31 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
37 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
74 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
117 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 ...
-4
votes
0answers
40 views

Sequence and Divisibility

Consider a sequence $a_1$, $a_2$, ..., $a_9$, $a_{10}$, with $a_1=a_{10}$, such that for $i \neq j$, $a_ia_j$ is divisible by $n$ if and only if $|i-j| \neq 1$. What is the minimum value of $n$?
6
votes
1answer
72 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
36 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
80 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. ...
3
votes
4answers
74 views

Solutions of $2^a - 7 = 27b$

How can I find the solutions of the equation $2^a - 7 = 27b : a, b \in \mathbb{N}$? I can see this is also of the form $2^a - 7 \equiv 0 \mod 27$.
0
votes
2answers
27 views

Verifying integer solutions to linear equations

Suppose I have the equation $B = \frac{8A - 29}{27}$, where $A$ and $B$ are integers. Then $27B = 8A - 29$, and so we have the linear Diophantine equation $8A - 27B = 29$. Using the extended ...
4
votes
5answers
77 views

An integer when divided by $5$ and $13$ leaves residues $4$ and $7$ respectively

Find an integer when divided by $5$ and $13$ leaves residues $4$ and $7$ respectively. (Without Modular Arithmetic). I don't know if it is right, but i got this $$n=5x+4=13y+7$$ ...
0
votes
1answer
33 views

Write a floored integer division in function of two divisions?

Is there any method to calculate the floored integer division for the sum of two numbers given the floored division of the summands, without splitting into cases? I know that, with floored division, ...
3
votes
1answer
21 views

Boundedness of $\gcd(|x-y|,|a_x-a_y|)$ in sequence

Let $a_1,a_2,\ldots$ be an infinite sequence of distinct positive integers, and let $n$ be a positive integer. Does there always exist integers $x,y$ such that $\gcd(|x-y|,|a_x-a_y|)>n$? When ...
2
votes
1answer
28 views

When is it possible to find a relatively prime pair among $n$ numbers?

Suppose I have a set of $n$ numbers and their gcd is $d$. If I divide every number by $d$, is it possible to find a pair that is relatively prime? Intuitively yes, but how do I prove it? I tried ...
-3
votes
5answers
93 views

Fastest way to check if 1501 is prime number? [closed]

What is the fastest way to check is 1501 is prime? I don't want to check for hours...
8
votes
1answer
56 views

Remainder when dividing by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$

Given a $54$-digit number consisting of only ones and zeros. Prove that the remainder when dividing this number by $33\cdot 34\cdot\ldots\cdot 39$ is greater than $100000$. The number can be written ...
2
votes
2answers
55 views

If $\gcd(a,n)=1$ then there exist integers $x,y$ such that $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y \pmod n$

If $a$ is integer and $n$ is positive integer such that $\gcd(a,n)=1$ then there exist integers $x,y$ for which $0<|x|,|y|<\sqrt{n}$ and $ax\equiv y\pmod n$. By Dirichlet's principle I ...
2
votes
2answers
75 views

Is a Number Divisible by 40

One of the "shortcuts" for determining if a number is divisible by 8 is to see if the last three digits are divisible by 8. One ...