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

learn more… | top users | synonyms (1)

17
votes
1answer
352 views

Are there $a,b>1$ with $a^4\equiv 1 \pmod{b^2}$ and $b^4\equiv1 \pmod{a^2}$?

Are there solutions in integers $a,b>1$ to the following simultaneous congruences? $$ a^4\equiv 1 \pmod{b^2} \quad \mathrm{and} \quad b^4\equiv1 \pmod{a^2} $$ A brute-force search didn't turn up ...
2
votes
2answers
124 views

solve congruence $x^{59} \equiv 604 \pmod{2013}$

This is an exercise from my previous exam; how should I approach this? Solve congruence $\;x^{59} \equiv 604 \pmod{2013}$ Thanks in advance :)
0
votes
1answer
105 views

Is sum and product of $k$ natural numbers always different from that of some other $k$ natural numbers?

Suppose $k$ is say $3$. Let $A,B$ be a sets of $3$ natural numbers. $A$ not equal to $B$. Can sum and product of the elements in $A$ be same as that of $B$. If the numbers are primes then the ...
2
votes
2answers
919 views

how to find remainder when $20! + 20^{23}$ is divided by $23$?

how to find remainder when $20! + 20^{23}$ is divided by $23$? I am finding it bit difficult to solve. Does any one has a simpler way to solve this problem??
2
votes
1answer
64 views

Question from number theory

Suppose $a, b, \text{and } c$ are integers with $0 < a < b < c$ and $\gcd(a,c)=\gcd(b,c)=1$. Show that one of the follows holds, $\gcd(a,b)=1$ or $\gcd(a,c-b)=1$ or $\gcd(c-a,b)=1$ or ...
1
vote
2answers
179 views

Does this inequality hold true, in general?

Let $$N = \prod_{i=1}^{\omega(N)}{{p_i}^{\alpha_i}}$$ be the prime factorization of the positive integer $N$. Does the following inequality hold true in general? ...
6
votes
2answers
257 views

$20$ hats problem [duplicate]

I've seen this tricky problem, where $20$ prisoners are told that the next day they will be lined up, and a red or black hat will be place on each persons head. The prisoners will have to guess the ...
3
votes
4answers
161 views

An identity wich applies to all of the natural numbers

Prove that any natural number n can be writen as $$n=a^2+b^2-c^2$$ where $a,b,c$ are also natural.
6
votes
3answers
153 views

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$?

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$? Can someone elaborate on this a bit?
1
vote
0answers
66 views

Translation/proof of elementary argument of Chebyshev

My question is whether the following proof is correct and how it might be better presented. This was an exercise to translate/shorten Chebyshev's argument that $\hspace{80mm} (1)$ $\hspace{55mm}\log ...
6
votes
3answers
320 views

bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ [duplicate]

I understand that both $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are of the same cardinality by the Shroeder-Bernstein theorem, meaning there exists at least one bijection between them. But I ...
1
vote
2answers
122 views

Equation $(a-3)cb=a(c+b)$ for natural numbers.

Let $a$, $b$, and $c$ be positive integers. Suppose that $c \leq b \leq a$ and that they satisfy the relation $$ (a-3)cb=a(c+b). $$ What can be said about the solutions?
2
votes
8answers
359 views

Prove that $9\mid (4^n+15n-1)$ for all $n\in\mathbb N$

First of all I would like to thank you for all the help you've given me so far. Once again, I'm having some issues with a typical exam problem about divisibility. The problem says that: Prove ...
5
votes
3answers
274 views

$a^2+b^3=c^5$Are there infinitely many solutions?

I am having troubles figuring whether there are infinitely many integer solutions to the following equation: $$a^2+b^3=c^5$$ This is just a problem I thought of on my own, so sorry in advance if ...
1
vote
3answers
151 views

Prove that MCD is 1 or 3 knowing (a,b) = 1

I'm don't know from where to start in this problem. I have to prove that $(a+b,a^2-ab+b^2)=1 \text{ or } 3$ knowing that $(a,b) = 1$. I've tried using the method they taught us on class, so ...
0
votes
1answer
145 views

Pascal's other triangle

Just a brainteaser question: Can you identify the generator of the following pattern of numbers?      Remark on any interesting patterns you see in the triangle.
1
vote
1answer
86 views

Prove inequality by induction

Once again, I'm stuck in a demonstration by induction, this time, it's really proving that an inequality is valid. So, here is the inequality: Prove that $\binom{2n}{n} \geq (n+5)^2 \ \forall n ...
1
vote
2answers
64 views

Is this inequality property true?

I'm having some trouble defining weather this inequality is true or not... Basically, I wanted to know if its true that if $a \geq b$ and $c \geq d \Rightarrow a + c \geq b + d$ Well, basically ...
1
vote
6answers
101 views

Proof by induction that the sum of terms is integer

I'm having some trouble in order to solve this induction proof. Proof that $\forall{n} \in \mathbb{N}$ the number $\frac{1}{5}n^5+\frac{1}{3}n^3 + \frac{7}{15}n$ is an integer. I've tried ...
28
votes
2answers
518 views

Find $a,b,c,d,e$ such that $\dfrac{s}a+1,\dfrac{s}b+1,\dfrac{s}c+1,\dfrac{s}d+1,\dfrac{s}e+1$ are all perfect squares $ (s=abcde)$

Are there five distinct positive integers $a,b,c,d,e$ such that $\dfrac{s}a+1,\dfrac{s}b+1,\dfrac{s}c+1,\dfrac{s}d+1,\dfrac{s}e+1$ are all perfect squares ? $ (s=abcde)$ If ...
0
votes
3answers
39 views

Showing that if $3d = 1 \pmod{14416}$ then $d =9611$?

How do you calculate with modulus: $$3d = 1 \pmod{14416}$$ How to verify that $d =9611$?
3
votes
0answers
83 views

Triangular numbers and the harmonic mean

This morning somebody called my attention to the fact that $4T_n$ is the harmonic mean of $T_{2n}$ and $T_{2n+1}$, where $T_n=n(n+1)/2$ is the $n$th triangular number. I verified this algebraically ...
2
votes
1answer
167 views

Floor Inequalities

Proving the integrality of an fractions of factorials can be done through De Polignac formula for the exponent of factorials, reducing the question to an floored inequality. Some of those inequalities ...
2
votes
1answer
63 views

Irrational sum to integers?

Is it possible for $(a-b)k + bf$ to be an integer if $k,f$ are irrational numbers and $a,b$ are integers? What about $(a-b)k - bf$?
1
vote
0answers
54 views

Looking for an algebraic proof of an unusual equality [duplicate]

I have stumbled on the equality $[\sum i]^2 = \sum i^3$ which holds when both sums are over the range 1 to k. The equality is readily demonstrated inductively, but I wonder if anyone can provide an ...
5
votes
4answers
388 views

Solutions to $p+1=2n^2$ and $p^2+1=2m^2$ in Natural numbers.

$$p+1=2n^2$$$$p^2+1=2m^2$$ Find positive integers $m,n$ and prime $p$ satisfying the above two equations. What would people commonly do? Subtracting both the equations. You get: ...
4
votes
2answers
180 views

What is the need for classifying numbers like integer, whole number etc?

what are the everyday life examples where we use the classification. I feel all the math behind the scenes(in computers weather etc ) is highly abstracted. I am looking for strong answers to tell the ...
0
votes
1answer
157 views

Divisibility of the difference of powers

Consider the following theorem: For any $a, b \in \mathbb{Z}^+$, there exist $m, n \in \mathbb{Z}$ such that $m > n$ and $a\ |\ b^m - b^n$. What's the best way to prove it? I have an idea ...
5
votes
2answers
99 views

For which rationals $x$ is $3x^2-7x$ an integer?

The following exercise is from [Birkhoff and MacLane, A Survey of Modern Algebra]: For which rational numbers $x$ is $3x^2-7x$ an integer? Find necessary and sufficient conditions. I think I ...
1
vote
3answers
130 views

Definitions of the usual order in $\mathbb{N}$

I know of basically two ways of defining the usual order in $\mathbb{N}$: By using the relation "$\in$" on $\mathbb{N}$ so that $\forall m,n\in N(m<n\longleftrightarrow m\in n)$. By saying ...
3
votes
1answer
112 views

Some questions about $\gcd(n,m)$ and $\phi(n)$

I was messing around in Excel at the end of work today and made a table where the $(i,j)$ entry $a_{i,j}$, for $j \geq i$, is 1 exactly when $i$ and $j$ are coprime (see snapshot of a portion of the ...
1
vote
1answer
690 views

The product of integers relatively prime to $n$ congruent to $\pm 1 \pmod n$

Problem: Let $1 \leq b_1 < b_2 <...< b_{\phi(n)} < n$ be integers relatively prime with n.Prove that $$B_n = b_1 b_2 ... b_{\phi(n)} \equiv \pm 1 \bmod n $$ I was thinking of Fermat's ...
1
vote
0answers
98 views

gcd finding method

An integer $d$ is a $\gcd$ of two non-zero integers $a$ and $b$, if $d$ divides $a$ & $d$ divides $b$ '$c$ divides $a$ & $c$ divides $b$' implies '$c$ divides $d$' for any integer $c$. If ...
3
votes
1answer
141 views

A generalization of Waring's problem

Let $f(x)$ be a polynomial with integer coefficients such that $$\lim_{x\to +\infty}f(x)=+\infty.$$ Is it true that there always exist two integers $K$ and $R$ (depend on $f(x)$), such that every ...
1
vote
1answer
58 views

Primitive Roots of a Prime P

The question is: Assume that p is an odd prime and that g is a primitive root for p. Also assume that $$ g^{149} \equiv g^{-1} \pmod p.$$ Find all possible choices of p. I don't want the ...
2
votes
1answer
50 views

Understanding a proof about the Broccard problem

I was reading the paper by Berndt and Galway,"The Brocard–Ramanujan diophantine equation $n!=m^2$. And I got stuck in the part when it says: (1)$$n!+1=m^2$$ (2)$$\left ( \frac{n!+1}{p} \right)=1 ...
1
vote
1answer
65 views

Finite ways to write $1 =\sum_{i=1}^{h}\frac{1}{n_i}$

Let $h\geqslant 1$ an integer. Can we show (simply), without using group actions, that there exists a finite number of decomposition of the form $\displaystyle 1 =\sum_{i=1}^{h}\frac{1}{n_i}$, ...
8
votes
8answers
511 views

Why is the Fibonacci ratio though a decreasing function, it is alternating and decreasing?

I tried to find the ratio of consecutive terms of the Fibonacci series and found that it is a decreasing function and it converges . I tried it though a small code piece in python so that I can have a ...
0
votes
1answer
53 views

Is this possible to find modulo of different value and get same result?

Is it possible, for $a,b,m,n,x,y\in\mathbb N$ to have $$x = y^a \pmod n \qquad \text{ and }\qquad y = x^b \pmod m ?$$ For example: $17=5^{11} \pmod{21}$ and $5=17^{11} \pmod{21}$ is an integer but ...
11
votes
1answer
2k views

what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

Can any one please tell the approach or solve the question what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by $47$? I can solve remainder of $45!$ divided by $47$ using wilson ...
2
votes
3answers
1k views

For what integers $n$ does $\phi(2n) = \phi(n)$?

For what integers $n$ does $\phi(2n) = \phi(n)$? Could anyone help me start this problem off? I'm new to elementary number theory and such, and I can't really get a grasp of the totient function. I ...
1
vote
2answers
53 views

$a, b, c, d$ are positive integers, $a-c|a b+c d$, and then $a-c|a d+b c$

$a, b, c, d$ are positive integers, $a-c|a b+c d$, and then $a-c|a d+b c$ proof: really easy when use $a b+c d-(a d+b c)$ however my first thought is, $a-c| a b+c d+k(a-c)$, and set some $k$ ...
0
votes
1answer
48 views

How many numbers can be divided by $k$ in $1, 2, \text{…}, n$?

How many numbers can be divided by $k$ in $1, 2, \text{...}, n$? $k=1$, there are $n$ numbers. $k=2$, there are$\left[\frac{n}{2}\right]$ $k=3$, there are $\left[\frac{n}{3}\right]$ $k=k$, there ...
1
vote
7answers
209 views

What does $a\equiv b\pmod n$ mean?

What does the $\equiv$ and $b\pmod n$ mean? for example, what does the following equation mean? $5x \equiv 7\pmod {24}$? Tomorrow I have a final exam so I really have to know what is it.
5
votes
1answer
252 views

direct proof $ x^2 \pm 1$ is not a perfect cube for integer $ x\geq 4$

by direct I mean wthout using any form of catalan's conjecture. Since all even cubes are multiples of $8$ so they are multiples of $4$. Therefore if the square is odd and smaller than the cube it ...
0
votes
1answer
300 views

Quadratic expression that generate primes

I recently learned that there exist quadratic expression that generate some primes and some of these equations generate more primes than others. In the following video, the person shows the following ...
4
votes
1answer
112 views

Prove $2^n > n^3$ for all $n \ge10$ [duplicate]

I am stuck with the this question: Prove by induction that $2^n > n^3$, for all $n \ge 10$ I got this far: Base: For $P(10)$: $$ 2^n > n^3 \\ 2^{10} > 10^3 \\ 1024 > 1000 $$ so, ...
4
votes
2answers
83 views

If $m \equiv n \pmod{A}$, then $s^m \equiv s^n \pmod{A}$?

I'm kind of stuck with the following assignment: Prove: If $m \equiv n \pmod{A}$, then $s^m \equiv s^n \pmod{A}$ I tried $m = k_1 \times A + r$ , and $n = k_2 \times A + r$ , then $s^m = s^{k_1 ...
4
votes
2answers
154 views

Number theory: if $(a,b)=1$, show that $(ac,b)=(c,b)$ [duplicate]

Mostre que, se $(a, b) = 1$, então $(a · c, b) = (c, b)$ Como posso fazer isso usando $(a,b) = 1\implies$ Existem $m,n$ naturais tais que $am - bn = 1$ Tentative translation: Show that if ...
2
votes
2answers
156 views

Propriedades do MDC (Properties of Greatest Common Divisor) [duplicate]

Estou com uma grande lista de exercícios de PROPRIEDADES DO MDC (MÁXIMO DIVISOR COMUM), e não estou conseguindo entender quais os passos que tenho que seguir nas demonstrações, e gostaria muito de ...