This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

3
votes
1answer
38 views

Frazzle game question

In $7^{th}$ grade, in order to learn divisibility, memory, and focus, my math teacher had my pre-algebra class play a game called Frazzle. To play the game Frazzle, each person went around the room ...
1
vote
0answers
34 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
0
votes
0answers
25 views

Rabin's cryptography - when the message $M$ isn't coprime to $n = pq$

Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$? say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$. ...
1
vote
4answers
79 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
2
votes
2answers
191 views

Fermat's little theorem

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
0
votes
3answers
53 views

Are there any divisibility rules using 7? [duplicate]

Divisibility rules of 1,2,3,4,5,6,8,9 are first or second grade math. Are there any divisibility rules for numbers with factors including 7. I noticed that the digits of 7x starting with x=1 to x=5 ...
3
votes
2answers
26 views

GCD of many numbers divisible by another number

$a$ is an integer such that: $$a \mid \gcd(b_1,b_2,\ldots,b_z)$$ and $z$ can be very large. Does the GCD approach $a$ as $z$ grows? If yes, what is the relation between $z$ and $a$? Thanks...
1
vote
1answer
48 views

Can we always write $gcd(x,y)$ as $ax+by$ in UFD?

Let $R$ be a commutative ring with unity. Now assume that $R$ is Unique Factorization Domain, but not necessarily Principal Ideal Domain. Question: Let $x,y\in R$ be such that their GCD exists in ...
2
votes
2answers
61 views

Number Theory- Mathematical Proof

I am trying to prove a theorem in my textbook using another theorem. What I need to show that if a,b, and c are positive integers, show that the least positive integer linear combination of a and b ...
1
vote
1answer
12 views

Is there a way to figure out the number of possible combinations in a given total using specific units

I'm not professional mathematician but I do love a math problem - this one, however has me stumped. I'm a UX Designer trying to figure out some guidelines for using tables in a page layout. The thing ...
1
vote
0answers
47 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
1
vote
1answer
89 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...
0
votes
3answers
47 views

Find remainder of $\frac{17^{235}}{ 23}$

I need to find remainder of $\frac{17^{235}}{ 23}$. This is supposed to be solved using the following method: $\varphi(23) = 22$ ${17}^{235} = (({17}^{22})^{10})\cdot {17}^{15}$ ${17}^{22}\equiv 1 ...
0
votes
1answer
33 views

Division with dividend less than divisor

Let $a\geq b$. We define the division of $a$ by $b$ to be, $$a=bq+r,$$ where $q,r$ are integers and $0\leq r<b$. How we divide $a$ by $b$ when $a<b$.?
0
votes
0answers
11 views

Given An initial point and final point ,How to determine the number of Co-Ordinates(x,y) such that both x and y are integral?

I have thought a lot about it and still no clue. I thought of visualising the initial point and the end point in the form of a Grid. But ,soon I was over with my resources. Problem: Given an initial ...
5
votes
3answers
101 views

If $a^b=c^d$, then $c$ and $a$ are powers of the same number?

I want to know in which situations two numbers that can be expressed as powers can be equal. I think it's intuitive that if two powers (say $a^b$ and $c^d$) are equal, then the bases must be ...
1
vote
1answer
25 views

Do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm?

As the title says, do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm? For example, we have $\gcd(24,17)$, so we can find $x,y$ such that $24x+17y=1$. ...
0
votes
2answers
488 views

Question of remainder on dividing by 7

Question : What is the remainder when $$ 10^{10} + 10^{10^2} +10^{10^3} + \ldots + 10^{10^{100}} $$ is divided by $7$?
-2
votes
0answers
19 views

Squares, Divisibility, and Fundamental theorem of arithmetic [duplicate]

I want to prove that if $a^2 | b^2$ then $a|b$. Is there an easy way to do this without using the fundamental theorem of arithmetic?
1
vote
3answers
60 views

HCF of two huge numbers

A question goes like : Find the HCF of $\underbrace{111\ldots 11}_{100\text{ ones}}$ and $\underbrace{111\ldots11}_{60 \text{ ones}}$. The answer is $\underbrace{111\ldots11}_{20 \text{ ones}}$ I'd ...
3
votes
2answers
529 views

The sum of digits of $3(3x+3)$ is always $9$ for any $x$ between $1$ and $9$

Given the following 'joke' I stumbled across today It's easy enough to figure out that the answer is always 9. Asshole. However when I tried to 'prove' this for ...
2
votes
5answers
303 views

Triple fractions

I've got this simple assignment, to find out the density for a give sphere with a radius = 2cm and the mass 296g. It seems straightforward, but it all got hairy when i've got to a fraction with three ...
1
vote
0answers
25 views

Example of binary GCD for complex integers?

I know you can use bit shifting to speed up the GCD algorithm for a pair of integers. Is there a way to apply this idea to gaussian integers?
4
votes
5answers
78 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
1
vote
0answers
79 views

$p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?

Let $p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?
8
votes
4answers
354 views

Find the sum of reciprocals of divisors given the sum of divisors

Let $d_1, d_2, \cdots d_k$ be all the factors of a positive integer '$n$' including $1$ and $n$. Suppose $d_1 + d_2 + d_3+\cdots+d_k = 72$. Then find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + ...
2
votes
1answer
42 views

A number root of two irreducible polynomials?

I woke up today doing me a question: is there a complex number that is root of two different irreducible polynomials of $\mathbb{Q} [x]$? I think not but I'm not sure and I am trying to prove. Some ...
1
vote
3answers
49 views

Divisibility of a polynomial by another polynomial

I have this question: Find all numbers $n\geq 1$ for which the polynomial $x^{n+1}+x^n+1$ is divisible by $x^2-x+1$. How do I even begin? So far I have that $x^{n+1}+x^n+1 = ...
2
votes
1answer
62 views

Show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ [duplicate]

Let $x_1,...,x_n$ be a natural numbers, show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ I know $\prod \left(x_i-x_j\right)$ is the result of ...
2
votes
3answers
88 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
-6
votes
3answers
75 views

Is 0/0 equal to 100%? [duplicate]

I've asked a heap of people this question and I can't get a definite answer. Some say it's 0%, 100% or just undefined. I know that Anything divided by zero is undefined. Anything divided by itself ...
-1
votes
1answer
34 views

If $\gcd(a,4)=\gcd(b,4)=2$, find $\gcd(a+b,4)$.

If the greatest common divisor (GCD) of $a$ and $4$ is $2$, and that of $b$ and $4$ is $2$, what is the GCD of $a+b$ and $4$? I tried writing $4$ as $2^2$. So GCD of $a$ and $2^2$ is $2$ and GCD of ...
0
votes
0answers
25 views

Divisibiltiy of the order of elements in a group

Let $G$ be a finite group and ket $y \in G$. How many elements $x \in G$ are there such that the order of $y$ is divisible by the order of $x$
-4
votes
2answers
51 views

g.c.d of two numbers [closed]

Let $n$ and $m$ be two integer numbers, is one of the following always true? 1) $\gcd(n,m)=1$ 2) $\gcd(n−1,m)=1$ 3) $\gcd(n,m−1)=1$ 4) $\gcd(n−1,m−1)=1$
0
votes
2answers
54 views

If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$

I need to show that: If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$ where $a,b,c$ are positive integers. I've come up with this, but I'm not 100% sure that it's correct: Assume $a\mid b$, then $a ...
2
votes
2answers
47 views

If $a\mid b+c$ and $\gcd(b,c)=1$, prove $\gcd(a,b)=\gcd(a,c)=1$

I have the following: $b+c=av$ for some integer $v$, and $a=dm$ and $b=dn$ for $d=\gcd(a,b)$ and some integers $m,n$. Then, $c=av-b=dmv-dn=d(mv-n)$. So, $d|c$, and we know that $d|a$ and $d|b$. I ...
3
votes
1answer
41 views

Prove that for any positive integer $n$ the number $1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$ is divisible by $2^{n-1}$.

Let $a=4k-1$, where $k \in \mathbb{Z}$. Prove that for any positive integer $n$ the number $$1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$$ is divisible by $2^{n-1}$. My ...
2
votes
0answers
30 views

Finding solutions to a symmetric divisibility condition $x\mid p(y),\;y\mid p(x)$

In general, are there strategies for finding all integers $x$ and $y$ such that $x \mid p(y)$ and $y \mid p(x)$ for some polynomial $p$ with integer coefficients? For example, could we find all ...
0
votes
2answers
103 views

When will $ax+1$ be divisible by $b$?

Consider two natural numbers $a$ and $b$ such that $b$ is prime and $a$ is indivisible by $b$. Then, for which integral values of $x$ should $ax+1$ be divisible by $b$ ? I tried different values of ...
4
votes
1answer
71 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
3
votes
2answers
65 views

Does $p^n$ divide $\binom{p^{n+m-1}}{m}$?

Let $n, m \in \mathbf N$ and $p$ an odd prime number. Then does $p^n$ divide $\binom{p^{n+m-1}}{m}$ ? It seems true, but I can not find a clue. Can I have any hint?
1
vote
5answers
129 views

Show that $30 \mid (n^9 - n)$

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step. Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$. Induction Step: Assuming ...
1
vote
0answers
31 views

Number of binomial coefficients , ${ n \choose k}$ k $\in$ [0,n] , that are divisible by a prime p?

For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n ...
1
vote
2answers
45 views

Is it true that $(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1$?

Notation: $(a,b) = \gcd(a,b)$ If $p,q$ are distinct odd primes, is it true that $$(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1\;?$$
4
votes
4answers
81 views

prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$

I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.
1
vote
0answers
42 views

using Fibonacci numbers prove that if $d|n$ then $F_d|F_n$ [duplicate]

The first question was to prove that $\gcd(F_{n+1},F_n) = 1$ So i tried to use it but with no success. any help or clue will appreciated thanks
3
votes
2answers
95 views

Which prime divides $18^{29}+1$? [closed]

I am struggling with the following problem. Any help will be appreciated. let $n= 18^{29}+1$. Prove that $n$ is divisible by $19$. Prove that if $ p $ is a prime which divides $n$, $p\ne19$,then $p ...
1
vote
1answer
52 views

When does $c\mid a(n+x)+b+1$, if we know that $c\mid an+b$?

If $an+b$ is divisible by $c$. Then for which values of $x$ will $a(n+x)+b+1$ be divisible by $c$? $a$, $b$, $c$, $n$, $x$ are all non-negative integers.
2
votes
1answer
18 views

Tools for dealing with a divisibility problem with powers of 2 and 3?

I'm trying to solve an equation with congruences: $$ \sum_{i=1}^{N}2^{\sum_{j=1}^{i} n_j}3^{N-i} \equiv 0 \; (\text{mod} \; 2^{\sum_{j=1}^{N}}-3^N) $$ The unpacked version (assuming ...
0
votes
0answers
18 views

If :$\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ how i deduce the remain of :$\sum_{k=1}^{n}k^{-p}$?

I have tried to determine the remain of this serie:$\sum_{k=1}^{n}k^p$ : I got this formula $\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ ,where $p$ is prime and $k$ is positive integer .Now ...