Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

2
votes
2answers
215 views

Greatest Common Factors and Least Common Multiples

$\mathrm{GCF}(a,b)=4$ and $\mathrm{LCM}(a,b)=96$. Find all pairs of whole numbers $a$ and $b$ for which both statements are true. I have no clue where to even start with this problem. Thank ...
0
votes
2answers
315 views

Modular Arithmetic Calendars

If a calendar has 427 days in the year and 8 days a week and the first day of their current year, which is 1027 falls on the second day of their week. What day of the week will the first day of the ...
3
votes
3answers
223 views

Why $ac=b^2$ forces $a,c$ to be squares if $a,c$ are coprime?

I was browsing this post: Prove that $a^2 + b^2 + c^2 $ is not prime number One of the answer has the following statement: "If the numbers $a$ and $c$ are coprime, then the equation $ac=b^2$ ...
6
votes
3answers
877 views

Prove that if $2^n-1$ is prime, then $n$ divides $2^n-2$

Suppose $p = 2^n - 1$ is prime. Show that $n \: | \: 2^n - 2$, or equivalently $n \: | \: p - 1$. With hint: The order of any element in this field divides $p-1$. Example: $n=7, \; p=127 ...
1
vote
0answers
86 views

An equation system in the integers

I am trying to solve the following equation system for an integer $k$: $$\begin{align*} k \alpha &\equiv 0\pmod{n}\\ \beta \frac{r^{k \alpha} - 1}{r^\alpha - 1} &\equiv 0 \pmod{m} ...
7
votes
2answers
299 views

Does $\varphi(mn) = \varphi(m)\varphi(n)$ imply that $\gcd(m,n) = 1$?

I know that Euler's totient function is multiplicative, in other words $\varphi(mn) = \varphi(m)\varphi(n)$ whenever $\gcd(m,n) = 1$. This is not true in general, for example $\varphi(2 \cdot 2) \neq ...
8
votes
0answers
196 views

Prime conjecture [closed]

I got this statement by upcoming mathematician Prof. Gandhi from BITS: "All twin primes from $17$ who are the smallest elements of a pair of twin primes, can be rewritten as: $(a + b + 1)$ such ...
3
votes
2answers
111 views

If $a|b$, $c|d$, $ab=cd$ and $\mathbb{Z}^*_a \times \mathbb{Z}^*_b \cong \mathbb{Z}^*_c \times \mathbb{Z}^*_d$. Does this imply $(a,b)=(c,d)$?

This question is inspired by $\mathbb{Z}_a\oplus\mathbb{Z}_b\cong \mathbb{Z}_c\oplus\mathbb{Z}_d$ question. We change the additive structure to multiplicative: Problem 1: If $a|b$, $c|d$ and ...
2
votes
2answers
301 views

Convolution of the Möbius function with itself

The Möbius function $\mu(n)$ is defined as: $μ(n) = 1$ if $n$ is a square-free positive integer with an even number of prime factors. $μ(n) = −1$ if $n$ is a square-free positive integer with an odd ...
1
vote
1answer
89 views

Calculate the quadratic irrational number given by a certain periodic cont. fraction

Calculate the quadratic irrational number $\alpha$ given by the periodic continued fraction $\alpha = \overline{ [1,2,1] } $. To be honest I am not sure how to tackle this one. I know the algorithm ...
5
votes
2answers
176 views

Finding $\lim_{n\to\infty}\Phi(n)/n^2$, When $\Phi(n)=\sum_{i=1}^{n}\phi(n)$

This exercise is meant to be 'explored' computationally. However, I implemented it in C++ and did not get anything better than a sequence of pseudo-random numbers. Let ...
1
vote
1answer
196 views

fermat's little theorem and residue classes

I am trying to understand fermat's little theorem in residue classes but the below slides make absolutely no sense to me. In computer classes a' means if you have 3 then 3' would be 6 because ...
2
votes
1answer
614 views

Solution to cubic Diophantine equation in two variables

Does anyone know how to solve the following cubic Diophantine equation in two variables: $$Ax^3 + Bx^2 + Cx + Dxy + Ey = 0$$ where A, B, C, D, E are known integers and $x$, $y$ are unknown integers ...
6
votes
2answers
97 views

A question about divisibility.

What I've observed: Pick any $3$ random positive integers, say $a$, $b$, $c$ which are not of the form $0\pmod{3}$ then one and only one of $a+b$, $b+c$, $c+a$, $a+b+c$ is always a multiple of $3$. ...
1
vote
2answers
142 views

Hundreds’ place digit of $1993^3 – 913^3 – 1083^3$

How can I find the hundreds’ place digit of the following number: $$1993^3 – 913^3 – 1083^3$$ I have not tried this one since I don't know how to begin. I can tell the units digit of this but ...
2
votes
3answers
1k views

GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

I was curious as to another method of proof for this: Given $a$, $b$, and $x$ are all natural numbers, $\gcd(ax,bx) = x \cdot \gcd(a,b)$ I'm confident I've found the method using a generic common ...
6
votes
2answers
994 views

On the factorial equations $A! B! =C!$ and $A!B!C! = D!$

I was playing around with hypergeometric probabilities when I wound myself calculating the binomial coefficient $\binom{10}{3}$. I used the definition, and calculating in my head, I simplified to this ...
4
votes
5answers
183 views

What are the possible values for $\gcd(a^2, b)$ if $\gcd(a, b) = 3$?

I was looking back at my notes on number theory and I came across this question. Let $a$, $b$ be positive integers such that $\gcd(a, b) = 3$. What are the possible values for $\gcd(a^2, b)$? I know ...
4
votes
2answers
244 views

Can it be proven (or disproven) that a particular digit is more prevalent than another digit in the set of all natural numbers?

This ties back to a SO question, where someone wanted to increase performance of an algorithm, and part of the solution was "test the most likely situation first". The question involved checking for ...
2
votes
4answers
3k views

the cube of integer can be written as the difference of two square

This Exercise $4$, page 7, from Burton's book Elementary Number Theory. Prove that the cube of any integer can be written as the difference of two squares. [Hint: Notice that ...
2
votes
2answers
510 views

Dickson's method for generating pythagorean triples can not find all triples - Known or not?

I recently came across Dickson's method on Wikipedia for generating pythagorean triples. I implemented this in a computer programming language and found some oddities, which was based on the fact that ...
2
votes
1answer
117 views

Is there no univariate integer polynomial that takes on the same positive values as the multivariate polynomial $x^2+y^2$?

Is there no univariate integer polynomial that takes on the same positive values as the multivariate polynomial $x^2+y^2$? The values are numbers such that each prime factor of the form $4k+3$ occurs ...
1
vote
2answers
83 views

Given $S=\left\{n\in\mathbb{N}:n<N\text{ and }\gcd(n,N)=1\right\}$, what is $\left|S\right|$?

Yesterday, in our modern algebra lecture, our professor asked us to find the number of positive integers $n<81$, such that $\gcd(n,81)=1$. Intuitively, I realized that I had to find the number of ...
4
votes
3answers
8k views

Find smallest number when divided by 2,3,4,5,6,7,8,9,10 leaves 1,2,3,4,5,6,7,8,9 remainder

Find smallest number when divided by 2,3,4,5,6,7,8,9,10 leaves 1,2,3,4,5,6,7,8,9 remainder.How to go about solving this problem??
6
votes
2answers
2k views

Derive a formula to find the number of trailing zeroes in $n!$ [duplicate]

Possible Duplicate: How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? I know that I have to find the number of factors of $5$'s, $25$'s, ...
0
votes
1answer
230 views

Understanding a Proof Regarding the Infinitude of Even Abundant Numbers

I was reading the following theorem. Theorem. There are infinitely-many even abundant numbers. Proof. For a positive integer $a$, let $n=2^a\cdot3$, and ...
2
votes
0answers
163 views

Primes $p$ such that $3$ is a primitive root modulo $p$ , where $p=16 \cdot n^4+1$?

How to prove following statement : Conjecture : Let $p$ be a prime number of the form : ${\color{BlueViolet}{p=16 \cdot n^4+1}}$ If $n$ is an odd prime greater than $3$ then $3$ is a ...
0
votes
1answer
372 views

The diophantine equation $a+b+c+d+e = abcde$

Now you may think that I am annoying, but if I am not asking this question, then it seems not so complete and I can't grasp the whole idea... refer to this question: Positive rationals satisfying ...
1
vote
1answer
138 views

Solving $ xy = a + b\cdot\operatorname{lcm}(x,y) + c\cdot\gcd(x,y)$ given $a,b,c$

Given $a$, $b$, and $c$, find the number of pairs of positive integers $(x, y)$ satisfying this equation: $$ xy = a + b\cdot\operatorname{lcm}(x,y) + c\cdot\gcd(x,y).$$ If $a=2, b= 1, c= 1$, then ...
2
votes
3answers
97 views

Invalid Proof involving Divisors?

Let $x, y \in \mathbb{Z}$. If $x \mid y^{2}$ then $x \mid y$. One counter example would be to let $x = 16$ and $y = 4$. We know that $16 \mid 16$, but $16 \nmid 4$. My question is what is wrong with ...
4
votes
1answer
192 views

Primes $p$ such that $2$ is a primitive root modulo $p$ , where $p=4\cdot k^2+1$?

Consider the prime numbers of the form : $p=4 \cdot k^2+1~$ , where $~k~$ is an odd prime number . For the first $~1200000~$ primes of this form except when $~p=4 \cdot 193^2+1~$ $2~$ is a ...
5
votes
1answer
351 views

Proving a Theorem about Perfect Numbers

I am trying to prove the following theorem: Theorem. A number is perfect iff the sum of the reciprocal of its divisors, excluding $1$, is $1$. Thus far, this is the proof that I have managed to ...
2
votes
2answers
344 views

Proving an Augmentation of the Sum of Divisors Function

Let $\sigma_{k}(n)$ denote the sum of the $k$th powers of the divisors of $n$, so that $\sigma_{k}(n)=\sum_{d|n}d^{k}$. Note that $\sigma_{1}(n)=\sigma(n)$. In a previous exercise, I was asked to ...
1
vote
1answer
286 views

What is the Sum of Divisors of a Composite Mersenne Number?

I am trying to show that if $n=2^{m-1}(2^{m}-1)$, where $m$ is a positive integer such that $2^{m}-1$ is composite, then $n$ is abundant. This is my proof thus far: Proof. Let $n=2^{m-1}(2^{m}-1)$, ...
1
vote
0answers
94 views

Primes $p$ such that $5$ is a primitive root modulo $p$ , where $p$ is a Woodall prime?

How to prove following statement : Let $~p~$ be Woodall prime of the form : $p=n\cdot 2^n-1$ $5~$ is a primitive root modulo $~p~$ iff $~n \equiv 3,6,9 \pmod {20}$ For example : $5$ is a ...
4
votes
2answers
268 views

question about primitive roots modulo p

I know that every group of units $\bmod p$ has a generator, in fact $\varphi(p-1)$ of them. I came across a problem that asked to prove that for such a generator, let's call it $a$ (but see below), ...
2
votes
3answers
871 views

Prove $(k,n+k)=1$ iff $(k,n)=1$

(a) Prove $(k,n+k)=1$ iff $(k,n)=1$. (b) Is it true that $(k,n+k)=d$ iff $(k,n)=d$? (all variables are integers, (a,b) means gcd(a,b)) For (a), I can only get so far. $(k,n+k)=1\ \Rightarrow\ ...
1
vote
2answers
131 views

Numbers of the form $x^x$

I was trying to come up with a way to show that $\sum_{i=0}^{n}i^i < cn^n$, where $c$ is some positive constant. I figured if this were true: $\sum_{i=1}^{n-1}i^i < n^n, n>1$ in other ...
5
votes
3answers
308 views

Find remainder when dividing $9^{{10}^{{11}^{12}}}-5^{9^{10^{11}}}$ by $13$.

Find remainder when dividing $$9^{{10}^{{11}^{12}}}-5^{9^{10^{11}}} \hspace{1cm} \text{by} \hspace{1.2cm} 13.$$ I tried transforming these who numbers separately to form $13k+n$ but failed.
5
votes
3answers
151 views

Does $x^2\equiv x\pmod p$ imply $x^2\equiv x\pmod {p^n}$ for all $n$?

Suppose $x^2\equiv x\pmod p$ where $p$ is a prime, then is it generally true that $x^2\equiv x\pmod {p^n}$ for any natural number $n$? And are they the only solutions?
11
votes
4answers
1k views

Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = ...
10
votes
1answer
267 views

Prove that there can't be 985 divisors of $123456…19841985$

Numbers from 1 to 1985 are written one after another so they form a new number, $n=123456\ldots19841985$. Prove that there can't be 985 divisors of $n$. This should be solved on paper, without ...
4
votes
1answer
336 views

How to prove that $\sum_{n=1}^{2012} \frac{1}{x_n} = 1 $ has finitely many solutions for positive integer $x_i$?

This is a homework problem. I tried proving this by means of induction. Verifying the case $n=1$ is easy, the only solution to $\frac{1}{x_1} = 1 $ is $x_1 = 1$, therefore there is only one, and thus ...
5
votes
0answers
511 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
0
votes
2answers
280 views

Linear congruences system

How do I solve a four-equation linear congruence system like the one below ? $$\begin{align*} a-2d &\equiv 5 \pmod{10}\\ -3a+3d &\equiv 8 \pmod{10}\\ 4a-4d &\equiv 6 \pmod{10}\\ -5a+d ...
1
vote
3answers
361 views

Solving modular equations

Is there a procedure to solve this or is it strictly by trial and error? $5^x \equiv 5^y \pmod {39}$ where $y > x$. Thanks.
1
vote
2answers
94 views

Let $d=(a,b)$, $b=\beta d$ and $n>1$. If $\beta$ is odd number, prove that $(n^a+1,n^b-1)\le 2$.

Problem. Let $d=(a,b)$, $b=\beta d$ and $n>1$. If $\beta$ is odd number, prove that $(n^a+1,n^b-1)\le 2$. Solution (from the book). Each common divisor of numbers $n^a+1$ and $n^b-1$ has to be ...
-1
votes
1answer
180 views

Demonstration of a divisibility rule

A friend of mine who's studying mathematics challenged me to demonstrate that: For given integer numbers $n$ and $m$, we can say $$\left(\prod_{i=n}^m i\right)/{(m-n)!} =Z,$$ where $Z$ is some ...
2
votes
0answers
211 views

Primality test for Generalized Fermat numbers using Chebyshev polynomials of the first kind?

One can prove following statements : $A)$ Let's define sequence $S_i$ as : $S_i = \begin{cases} 2, & \text{if }i = 0 \\ 2S^2_{i-1}-1, & \text{otherwise} \end{cases}$ $ M_p = ...
3
votes
1answer
299 views

Amicable Pairs (How many have been found so far?)

My question is simply, how many amicable pairs have been found so far using super computers? I have been trying to find any kind of answer online that is up to date, but after searching in depth I ...