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

learn more… | top users | synonyms

5
votes
1answer
533 views

Applying Euler's Theorem to Prove a Simple Congruence

I have been stuck on this exercise for far too long: Show that if $a$ and $m$ are positive integers with $(a,b)=(a-1,m)=1$, then $$1+a+a^2+\cdots+a^{\phi(m)-1}\equiv0\pmod m.$$ First of all, I ...
3
votes
1answer
95 views

How fast is a low denominator encountered, when using only mediants?

This question is (remotely) related to How to find a "simple" fraction between two other fractions?, but is not answered in that older post. Let $f_1=\frac{a}{b}$ and $f_2=\frac{c}{d}$ be ...
1
vote
1answer
267 views

Quartic Diophantine equation in two variables

How would one solve the following quartic Diophantine equation in two variables: $$Ax^4 + Bx^3 + Cx^2 + Dx + Ey^2 + Ey = 0$$ where A, B, C, D, E are known integers and $x$, $y$ are unknown integers ...
1
vote
1answer
79 views

Multiplicity of Factors without Acutal Factoring

Is there a way to get the multiplicity of all prime factors of a given composite number, without doing the actual factorisation? For example $24$ would have multiplicities $(3,1)$, because of ...
4
votes
5answers
740 views

Is it possible to get 1/3 without dividing by 3?

So I need to divide a rectangle into 3 equals parts, but without fractions. It's one of those old "You have two jars of two sizes and need to get an exact amount of some other size" type problems, ...
6
votes
2answers
368 views

Divisibility of integers

Let $n > 1$ be an integer. Then $2^n - 1\nmid 3^n - 1$. I don't know how to prove it. Can anybody help me, please? In general, for a fixed positive integer $a > 1$, has $a^n - 1|(a +1)^n - 1$ ...
0
votes
0answers
59 views

Given that $x_{k+1}=P(x_k)$ show that $P(x)=x+1$ [duplicate]

Possible Duplicate: Iterated polynomial problem Let $P(x)$ be a polynomial with integer coefficients. For each positive integer $P(n)>n$. Consider the sequence defined by $x_1=1$ and ...
3
votes
1answer
96 views

Is there a direct proof of this inequality between quotients of integers?

Let $\frac{a}{b}$ and $\frac{c}{d}$ be two reduced fractions with $bc-ad > 1$ (and hence $\frac{a}{b} \lt \frac{c}{d}$) and $a,b,c,d$ positive. It is well known that there are integers $u,v$ ...
3
votes
0answers
166 views

The Mystery of the Número Cabalístico

I recently ran into an interesting type of number that people from where I was born like to refer to as números cabalísticos. They are supposedly "magic" kinds of numbers that possess mystical ...
4
votes
2answers
608 views

Find the last two digits of $12^{12^{12^{12}}}$ using Euler's theorem

I am suppossed to find the last two digits of $12^{12^{12^{12}}}$ using Euler's theorem. I've figured out that it would go as $12^{12^{12^{12}}} \mod{100}$. But I really don't know how to progress ...
2
votes
1answer
116 views

Quadratic equation with coefficients from FLT

Let $a,b,c>0$ be pairwise relatively prime and $n>2$ be odd. Can the equation, $a^n\cdot x^2+b^n\cdot x+c^n=0$, have rational roots $x$?
8
votes
4answers
271 views

A solution to $y^5 \equiv 2\pmod{251} $

I need to show that the following equation has a solution. (I am not asked for the answer, which I know by Mathematica to be $y=43$. ) $y^5 \equiv 2 \pmod{251}. $ I know that the order of 2 is 50, ...
7
votes
6answers
936 views

how to find out remainder of $3^{256}$ divided by $13$

here is a question that about finding the remainder when dividing $3^{256}$ divided by $13$. Can anyone suggest how to find the solution
13
votes
1answer
355 views

Roots with equal fractional parts

Question. ¿Does there exist an integer $n>1$ such that there exist positive integers $a,b$ such that $\{\sqrt[n]{a}\}=\{\sqrt[n]{b}\},a\neq b$ and $a$ and $b$ aren't perfect n-th powers? ( $\{x\}$ ...
6
votes
1answer
582 views

Are there any $n$ for which $ n^4+n^3+n^2+n+1$ is a perfect square?

Are there any positive $n$ for which $ n^4+n^3+n^2+n+1$ is a perfect square? I tried to simplify \begin{align*} n^4+n^3+n^2+n+1 &= n^2(n^2+1)+n(n^2+1)+1\\ &= (n^2+n)(n^2+1)+1 \\ &= ...
1
vote
1answer
156 views

Is $X_{n}\cap X_{m}=\emptyset$ for all $n\ne m$?

Let $$X_{r}=\{2^{r}(2s-1)-1:s=1,2,3,...\}.$$ Show that $X_{n} \cap X_{m}=\emptyset$ for all $n\ne m$ and also the union of $X_{i}$ $(i\in \mathbb N)$ is $2\mathbb N+1$. NB: $n$ is fixed. For a fixed ...
3
votes
4answers
365 views

Proving Multiplicativity of $\phi$ Using Euler's Theorem

Is it possible to show that $\phi$ is multiplicative using Euler's theorem? That is, can I show Theorem. Let $m$ and $n$ be relatively prime positive integers. Then $\phi(mn)=\phi(m)\phi(n)$ ...
2
votes
3answers
101 views

Showing $a\perp b$ and $n\ne 0$ implies $a+bk\perp n$ for some $k$

I'm stuck on a homework problem and I'm hoping to get a hint in the right direction. Assuming that $a\perp b$ ($a$ coprime with $b$), I would like to show that for all integers $n$, there is a ...
1
vote
4answers
113 views

using Fermat's little theorem to reduce a large number mod a prime

i want to show that $2^{70}\equiv 10 \pmod{13}$ using Fermat's little theorem. I see that $2^{12}\equiv 1 \pmod{13}$ hence $2^{60}\equiv 1 \pmod{13}$ so $2^{70}\equiv 2^{10} \pmod{13}$ but i don't ...
3
votes
1answer
179 views

confusion on legendre symbol

i know that $\left(\frac{1}{2}\right)=1$ since $1^2\equiv 1 \pmod2$ now since $3\equiv 1\pmod2$ we should have $\left(\frac{3}{2}\right)=\left(\frac{1}{2}\right)=1$ but on Maple i get that ...
3
votes
3answers
546 views

How to find a “simple” fraction between two other fractions?

If we have two fractions $a = { a_1 \over a_2} $ and $c = {c_1 \over c_2}$ with $a<c$, how to find the fraction $b = { b_1 \over b_2 }$ , $a < b < c$ for which some measure of ...
2
votes
4answers
1k views

$n$th Roots of Unity

I need to show that the product of all the $n$th roots of unity is $(−1)^{n+1}$. Is there a way to do this by induction? If there is, I can't seem to figure it out. Are there other, perhaps more ...
1
vote
1answer
409 views

Showing that $\tau(2^n − 1) \ge \tau (n)$

Let $n$ be a positive integer. Show that $\tau (2^n − 1) \ge \tau (n)$, where $\tau (n)$ is the number of divisors of $n$ including $n$ itself and $1$. I just can not seem to figure this one out any ...
2
votes
1answer
183 views

Complex Roots of Unity and the GCD

I'm looking for a proof of this statement. I just don't know how to approach it. I recognize that $z$ has $a$ and $b$ roots of unity, but I can't seem to figure out what that tells me. If $z \in ...
3
votes
1answer
236 views

Heronian triangles

How to prove that all Heronian triangles can be found using formulas described here? I understand that the described substitution will give Heronian triangle, but how to prove that using the ...
11
votes
7answers
750 views

Prove: $\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ is an integer for $n \ge 0$

I am attempting to prove the following problem: Prove that $\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ is an integer for all integers $n = 0,1,2,...$ I attempted to solve it by ...
3
votes
3answers
145 views

Pythagorean primitive triples

If $a,b,c$ are primitive Pythagorean triples such that $c^2=a^2+b^2$, prove that this is unique primitive Pythagorean triple using $c$ as hypotenuse. I'm not sure if I phrased this correctly. I want ...
3
votes
1answer
147 views

How to find minimum n that $\gcd(a+n^b, a+(n+1)^b) \neq 1$?

After reading an answer of a problem, saying that $\gcd(9+n^{17},9+(n+1)^{17}) = 1$ holds until n=8424432925592889329288197322308900672459420460792433, my first though was 'How the heck they found ...
1
vote
3answers
497 views

There are infinitely many triangular numbers that are the sum of two other such numbers

In the Exercise $9$, page 16, from Burton's book Elementary Number Theory he state the following: Establish the identity $t_{x}=t_{y}+t_{z},$ ($t_{n}$ is the nth triangular numbers) where ...
2
votes
0answers
403 views

A Quadratic diophantine equation

How to prove or disprove this statement: For all $c<z<0<s$, there exists $0<k\leq i$, $0\leq j<s+i$, such that all conditions hold simultaneously: ...
0
votes
1answer
161 views

Polyhedron with $11$ faces

Show that there is no polyhedron with exactly $11$ faces such that each face is a polygon having an odd number of sides.
2
votes
2answers
216 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
317 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
878 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
301 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
178 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
621 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
144 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
1k 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
246 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 ...