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)

1
vote
4answers
75 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=$ ...
0
votes
0answers
21 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
3answers
535 views

Simple Property of GCD and Modular Arithmetic

I'm stuck on proving a rather elementary property, as I'm not really sure how to start off the approach. Suppose $g^a\equiv 1$ mod $m$ and $g^b\equiv 1$ mod $m$. Does this imply that ...
46
votes
4answers
7k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
2
votes
2answers
186 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 ...
3
votes
2answers
21 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...
0
votes
0answers
22 views

How did this GCD formulae came about [duplicate]

A friend of mine was reading a book where a specific case of finding GCD is mentioned. The formulae goes as follows: $gcd(a^m - 1, a^n - 1 ) = a^K-1$ $where, K = gcd(m,n) $ Firstly, I wonder if ...
0
votes
3answers
51 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 ...
4
votes
1answer
27 views

What is the maximum value of the LCM of three numbers $\leq n$, as a function of $n$?

Given $n \geq 3$, what maximum LCM of any three numbers $\leq n$ can we obtain? Now, if $n$ is odd, the answer would be $$n(n - 1)(n - 2)$$ because $\newcommand{\lcm}{\operatorname{lcm}}$ ...
2
votes
2answers
58 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
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= ...
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 ...
2
votes
3answers
41 views

Prove for integers a, b, and c, if gcd(a, b) = 1, a|c, and b|c then ab|c

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$. Part b of this question is: "Is the converse true? Prove or disprove accordingly?" Hey, so I've been drawing ...
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 ...
1
vote
0answers
46 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 ...
2
votes
1answer
37 views

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime. Here $v_p(k)$ denotes the largest $\alpha\in\mathbb Z_{\ge 0}$ s.t. $p^\alpha\mid k$. We have ...
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 ...
5
votes
4answers
175 views

Finding the possible Least Common Multiples of of numbers with Highest Common Factor 8

The Highest Common Factor of two numbers is 8. Which one of the following can never be their Least Common Multiple? The choices are as follow: A. 8 B. 12 C. 60 D. 72 The answer key states ...
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$.?
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 ...
0
votes
0answers
10 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 ...
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 ...
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$. ...
4
votes
1answer
36 views

Solving a Diophantine equation with LTE

Show that only positive integer value of $a$ for which $$4(a^n+1)$$ is a perfect cube for all positive integers $n$, is $1$. Rewriting the equation we obtain: $$4(a^n+1)=k^3$$ It is obvious that $k$ ...
3
votes
2answers
525 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 ...
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$?
1
vote
3answers
59 views

HCF of two huge numbers

A question goes like : Find the HCF of $\underbrace{111...11}_{100\text{ ones}}$ and $\underbrace{111...11}_{60 \text{ ones}}$. The answer is $\underbrace{111...11}_{20 \text{ ones}}$ I'd like to ...
-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?
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 ...
57
votes
7answers
7k views

What makes $9$ special?

I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
3
votes
2answers
72 views

Why is the sum of the digits in a multiple of 9 also a multiple of 9?

The sum of the digits in $9 k$ (where $k$ is an integer) is a multiple of $9$: for example $$9\cdot 1=9$$ $$9\cdot 7=63 \qquad \text{and } 6+3=9\cdot 1$$ $$9\cdot 11=99 \qquad \text{and } ...
3
votes
4answers
71 views

prove that $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.
5
votes
2answers
1k views

Prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$

So, if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$ means $1=ax+by$, and want to show $a^2x+b^2y=1$. By squaring $1=ax+by$ both sides, I get, $1=(ax)^2+b(2axby+by^2)$. It doesn't help my proof. Please help ...
2
votes
1answer
60 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 ...
1
vote
0answers
17 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
69 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 ...
2
votes
2answers
627 views

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$ I think I got it, but is this proof correct? We can write any integer x in the form: $x = 6k, x = 6k + 1, x = 6k + 2, x = 6k + 3, x = 6k + ...
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 ...
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 ...
4
votes
6answers
125 views

Prove $7|x^2+y^2$ iff $7|x$ and $7|y$

The question is basically in the title: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$ I get how to do it from $7|x$ and $7|y$ to $7|x^2+y^2$, but not the other way around. Help is appreciated! Thanks.
2
votes
4answers
92 views

If the sum of two squares is divisible by $7$, both numbers are divisible by $7$ [closed]

How do I prove that if $7\mid a^2+b^2$, then $7\mid a$ and $7\mid b$? I am not allowed to use modular arithmetic. Assuming $7$ divides $a^2+b^2$, how do I prove that the sum of the squares of ...
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
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 ...
1
vote
2answers
49 views

Properties of Greatest Common Divisors

I really want to have help verify these properties of GCD: Let $s,t \in \mathbb{Z}$ and $m,n$ be positive integers with $m|n$. If $\gcd(t,n)|\gcd(s,n)$, then $\gcd(t,m)|\gcd(s,m)$. If ...
1
vote
3answers
25 views

Greatest common Divisor of negative numbers

To find gcd of negative numbers we can convert it to positive number and then find out the gcd. Will it make any difference?
-6
votes
3answers
74 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 ...
3
votes
1answer
47 views

Smallest $a$ such that both $a$ and $a+5$ and $a$ and $a+7$ have a common factor

Which is the smallest integer number $a$ so that the highest common factor of $a$ and $a+5$ is not $1$ and the highest common factor of $a$ and $a+7$ is not $1$ either? I think that it is $35$. Am I ...