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

learn more… | top users | synonyms (1)

1
vote
0answers
26 views

I'm interested in the solution set satisfying the equation $\log_{10} p\times\log_{10} q=\log_{10} r$

The equation interested in is $\log_{10} p\times\log_{10} q=\log_{10} r$ where $p,q,r\in\mathbb N$ are natural numbers. Here, I want not to consider some trivial solutions that make any one of ...
0
votes
2answers
65 views

Let $ k $ belong to the naturals. Prove that $3k^2+2$ is never a perfect square

I'm been struggling with this proof for a couple of hours. I originally thought I could prove it by contradiction and let some $n^2=3k^2+2 $to prove there is a contradiction, but it got me nowhere. ...
2
votes
1answer
44 views

Does the standard argument behind Bertrand's Postulate show that $\pi(2x)-\pi(x) > \frac{2n\log 2}{3\log 2n} -\sqrt{2n} - 1$

The standard argument for Bertrand's Postulate gives: $$\left(\prod\limits_{2n \ge p > n} p\right)\left(2^{\frac{4n}{3}}\right)\left((2n)^{\sqrt{2n}}\right) > { {2n} \choose {n} } = ...
4
votes
0answers
155 views

Diophantine equation: $7^x=3^y-2$

I've tried using mods but nothing is working on this one: solve in positive integers $x,y$ the diophantine equation $7^x=3^y-2$.
7
votes
0answers
187 views

when $F_n^2+F_m^2$ is a square for fibonacci numbers

This is a curiosity question I'm trying to solve a Diophantine equation and I need some results about fibonnacci numbers, I encountered this problem: For which couple of integers $(n,m)$ the ...
0
votes
0answers
25 views

Formula for Maximum of $n$ numbers

How do I find the formula for the $kth$ ($0<k,n+1, k$ integer) maximum of of $n$ numbers? I developed a formula for $n=2$ and $n=3$. But when I try to formulate for $n=4$ the formulae becomes ...
2
votes
1answer
65 views

$\beta \mathbb {N}$ is compact

I want to show the compactness of the set $\beta \mathbb N := \{ \mathcal U \mid \mathcal U \text{ is an ultrafilter on } \mathbb N \}$, with the topology induced by the basis $U_M = \{\mathcal U \in ...
0
votes
0answers
29 views

Determine when a prime divides this

Let $x$ and $y$ be integers, and consider the expressions $A=192x+a$ and $B=192y+b$, where $a,b$ are nonnegative mod $192$ residues (so $a,b\in \{0,1,2,...,191\}$). For which ordered pairs $(a,b)$ ...
1
vote
0answers
40 views

four different integers exist, what is the least product value? [duplicate]

Four different positive integers $a, b, c, d$ are such that $a^2 + b^2 = c^2 + d^2$. What is the smallest possible value of $abcd$? $$a^2 - c^2 = d^2 - b^2$$ $$(a-c)(a+c) = (d-b)(d+b)$$ ...
0
votes
0answers
20 views

Need Help Checking my Congruence Proof

Question: Let $p$ be an odd prime and $a$ be any integer which is not congruent to $0 \bmod p$. I need to prove that the congruence $x^2 ≡ −a^2(\bmod p)$ has solutions iff $p ≡ 1 (\bmod 4)$. Hint: ...
3
votes
1answer
233 views

Help with a simple number theory proof

Prove, that no matter how we give $8$ three-digit numbers, we can always choose $2$ of them, which we write next to each other, that six-digit number will be divisible with $7$. Example: I have $123$, ...
1
vote
2answers
58 views

Prove $f(x)$ is a square

For my first part of my question, I have to prove that if $a$ is any integer and the polynomial $f(x) = x^2 +ax+ 1$ factors (mod 8), then $f(x)$ is in fact a square; so what that means is that $f(x) ≡ ...
0
votes
1answer
41 views

Prove congruence $x^2 ≡ −a^2(\bmod p)$

Let $p$ be an odd prime and $a$ be any integer which is not congruent to $0 \bmod p$. I need to prove that the congruence $x^2 ≡ −a^2(\bmod p)$ has solutions iff $p ≡ 1 (\bmod 4)$.
-1
votes
2answers
40 views

How can we prove that these series are convegent?

Let $r>4$ be a positive integer. How we can prove that these series are convegente: 1) $$S=\sum_{m=1}^{∞}\frac{1}{r^{m^2}}$$ 2) $$D=\sum_{m=1}^{∞}\frac{(p_{m}-2(m-1))}{r^{m^2}}$$ where $p_{m}$ ...
0
votes
0answers
21 views

Verification on $\phi$ proof [duplicate]

I need to find a positive integer $n$ such that $ϕ(n) = ϕ(n + 1) = ϕ(n + 2)$ where $ϕ(n)$ denotes Euler's totient function. What I am given: (1) You may take $ϕ(n) = 2592$. (2) $ϕ(2n) = ϕ(n)$ ...
0
votes
0answers
20 views

Natural number starts with 1 or zero? [duplicate]

I know positive integers are 1,2,3,4,....;and the sequence of whole numbers are -3,-2,-1,0,1,2,3,...;But the Natural numbers start with one 0r zero ?
3
votes
0answers
83 views

Show that $a^2 + b^2 = c^3 $ has infinitely many solutions [duplicate]

Show that $a^2 + b^2 = c^3 $ has infinitely many solutions in $ \{ (a,b,c) \in \Bbb Z ^3 | (a,b)=1, (a,c)=1, (b,c)=1 \}$ . Describe all these solutions. I don't know how to approach this question. ...
0
votes
2answers
62 views

Courant's proof of irrational number

In Courant's Differential and Integral Calculus he proves that if a right-angle triangle has sides of unit 1 length then, using Pythagoras, we have $ h^2 = 1^2 + 1^2 = 2 $. Now, if $h$, the ...
4
votes
2answers
91 views

A tale of two palindromes (sum of squares of two palindromes is a perfect square).

I am just curious on wether there are infinitely many palindromes say $p_1$ and $p_2$ satisfying: $p_1^2+p_2^2$ is a perfect square with $\gcd(p_1,p_2)=1$. I believe that there are some but, are ...
1
vote
3answers
38 views

nearly equal arithmetical expressions

This is for teaching math. I'm wondering if someone knows some striking near-equalities between simple arithmetic expressions. I vaguely remember that such things exist (e.g., numbers that look alike ...
0
votes
2answers
67 views

How to solve this quadratic congruence modulo a non-prime number

$(1)$ Find all $x$, that solve $7x^2 + x + 22 \equiv 0 \pmod{60}$. I tried to solve this by first considering the prime factorization $60 = 2^2\cdot 3\cdot 5$ and then using the Chinese Remainder ...
-1
votes
2answers
52 views

Prove $p ≡ 1 (\bmod 4)$

Suppose that $a$ and $b$ are two integers with GCD 1. Prove that if $p$ is any odd prime which divides $a^2 + b^2$, then $p ≡ 1 (\bmod 4)$. Hint: We cannot conclude that $a^2 + b^2$ is a prime ...
1
vote
2answers
28 views

Are all roots of unity (solutions to $a^k \equiv 1$) for a prime modulo $p$, a multiple of $p-1$??

If $a$ is coprime to $p$, and $a \not \equiv 1,-1 \mod p $ then are there any solutions to $a^k \equiv 1 \mod p $ such that $0< k < p-1$? For any counterexample, it is obvious $GCD(p-1, k) \not ...
7
votes
3answers
131 views

When does $A(x^2+y^2+z^2)=B(xy + yz + xz)$ have nontrivial integer solutions?

Someone on MathematicaSE asked for which coprime integer pairs $(A,B)$ satisfying $A<B$ the equation $A(x^2+y^2+z^2)=B(xy + yz + xz)$ admits nontrivial integer solutions. The question was closed ...
1
vote
2answers
103 views

What mistake am I making when trying to apply Fermat's little theorem?

This is a problem from Discrete Mathematics and its Applications This is Fermat's little theorem from https://www.youtube.com/watch?v=w0ZQvZLx2KA, Here is my work so far First 41 is prime and ...
1
vote
2answers
56 views

$m<n$ and $n<r \implies m<r$

I have to demonstrate $$m<n \land n<r\Rightarrow m<r$$ where $m,n,r \in \mathbb Z$ using order definition of an integer. Attempt: $$\\m<n\hspace{.3cm}if \hspace{.3cm}m \le n ...
1
vote
2answers
47 views

Can someone verify the reasoning of why these two congruences are equivalent?

I've wondered why two congruences like $x\equiv81\pmod {53}$ and $x\equiv28\pmod{53}$ were equivalent. I've come up with this proof. I am not sure if this is how you prove it though I know that ...
2
votes
3answers
220 views

Prove that in an arithmetic progression of 3 prime numbers the common difference is divisible by 6

Here's the question from the book: Three prime numbers $p, q$, and $r$, all greater than 3, form an arithmetic progression: $$\begin{align} p&=p \\ q&=p+d \\r&=p+2d \end{align}$$ ...
3
votes
2answers
77 views

How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility. Example: Find the first Fib number that is divisible by $x=223321$, with no ...
0
votes
2answers
50 views

Is this true ? $a^3c \pmod{ab} = a^3c \pmod{b}$

Is this true ? $a^3c \pmod{ab} = a^3c \pmod{b}$ Actually I was working on this and got confused in my previous question... This seems to be true...Is it easy to verify/prove ? Thanks! $a | a^3c$ ...
1
vote
1answer
30 views

Is this true ? $a^3c \pmod{ab} = c \pmod{b}$

Is this true $a^3c \pmod{ab} = c \pmod{b}$ ? I noticed this today and it seems to be true as all the examples I have tried worked... Is there an easy way to make sense of why this true ? Thanks!
8
votes
2answers
151 views

Last digit of $3^{459}$.

I am supposed to find the last digit of the number $3^{459}$. Wolfram|Alpha gives me ...
2
votes
1answer
75 views

Generalization of Euler's totient theorem (aka Fermat–Euler theorem)

I am solving some math competition questions, and I realized that I do not know of a rigorous solution for this problem: What is the units digit of $2^{2015}$? We can easily see that the units ...
1
vote
1answer
44 views

Run time/Efficiency of finding Least Common Multiple

The algorithm is: $$\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}$$ And we can use the Euclidean algorithm for finding $\gcd$. How is the complexity for above method $O(n^3)$, if $x,y$ can at ...
2
votes
3answers
70 views

Proof that $\phi (n) \neq 50$?

Like the question states, I'm curious how to go about doing this. I found so far that if such an n does exist, then $n \in \Big[51,219 \Big]$, but I'm not sure if I took the right route with this ...
0
votes
1answer
28 views

Distinct non-negative integers $y<9$ such that $f(y) ≡ 0 (\bmod 9)$.

Prove that if $a$ is any integer and the polynomial $f(x) = x^2 +ax+ 1$ factors (poly mod 9), then there are THREE distinct non-negative integers $y$ less than $9$ such that $f(y) ≡ 0 (\bmod 9)$.
6
votes
3answers
195 views

The number $90$ is a polite number, what is its politeness?

The number $90$ is a polite number, what is its politeness? A. $12$ B. $9$ C. $6$ D. $14$ E. $3$ How did you get that answer? I tried Wikipedia to figure out what a polite number was ...
3
votes
1answer
62 views

When is $(12x+5)/(12y+2)$ not in lowest terms?

I am struggling to solve this problem and would appreciate any help: When is $\frac{12x+5}{12y+2}$ NOT in lowest terms? (x,y are nonnegative integers) I have found that it is not in lowest terms for ...
0
votes
1answer
55 views

Covariant and countervariant interpretations of SEQ in AR

Let a covariant interpretation of model $\mathscr{M}$ in model $\mathscr{M}'$ be defined as a couple of functions $(f,g)$, with $f$ injective, such that ...
1
vote
2answers
44 views

Linear congruence fill in the missing step?

Currently working on this problem and I'm having trouble seeing how it goes from one line to the next. $45x \equiv 63\mod 11$ goes to $x \equiv 8\mod 11$ Any help would be awesome thanks. ...
2
votes
3answers
27 views

How to solve this linear congruence equation and more general cases?

Okay so I'm trying to solve $5x \equiv 7 \mod 11$ and this is the particular example that I can't do. Can someone help me learn how to solve these and more general examples $ax \equiv b \mod n$. I ...
0
votes
2answers
61 views

Find roots of polynomial

Let p be an odd prime number and $ζ =ζ_p = cos(2π/p)+isin(2π/p)$ How do you find all of the roots of the polynomial $f(x) = x^{p-1} +x^{p-2}+…+x+1$ How do you show that $p = (1-ζ)(1-ζ^2)…(1-ζ^{p-1}) ...
6
votes
2answers
139 views

Is there $a,b,c,d\in \mathbb N$ so that $a^2+b^2=c^2$, $b^2+c^2=d^2$? [duplicate]

Question: Are there $a,b,c,d \in \mathbb N$ such that $$a^2 + b^2 = c^2 \ \ \text{and} \ \ b^2 + c^2 = d^2$$ I'm a bit lost here.
1
vote
3answers
65 views

If p is an odd prime, prove that $a^{2p-1} \equiv a \pmod{ 2p}$

Let $m = 2p$ If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$. I have no idea on how to start. I was trying to find a form such that $a^{m - 2} ...
0
votes
6answers
81 views

How to find the multiplicative inverse of $2^{29} \mod 9$

I just started studying this topic and from my understanding I have to find an integer $x$ such that: $2^{29}x \equiv 1 \mod 9$ However, I have no idea of how to find a linear combination of $9$ and ...
8
votes
6answers
152 views

Prove that $(n+1)^{n-1}<n^n$

How would one prove that $$(n+1)^{n-1}<n^n \ \forall n>1$$ I have tried several methods such as induction.
0
votes
2answers
61 views

Computing $22^{201} \mod (30)$

I am having trouble, I tried using the fact that the $gcd(30, 22) = 2$ but I have been stuck here for a bit now. $22^{201} \equiv x \mod (30)$ $22^{201} \equiv 22*22^{200} mod (30)$ How can I ...
3
votes
1answer
56 views

System of Exponential Equations in $x$ and $y$

Three of the elements in the solution set of the simultaneous system $x^{x+y} = y^4, y^{x+y} = x$ are ordered pairs of integers $(x, y)$. Find these ordered pairs. I found the trivial solution at ...
2
votes
1answer
49 views

Which integers can be written in two different ways as a sum of $n$ distinct factorials?

Problem 11 from the 1966 IMO Shortlist asks: Does there exist an integer $z$ that can be written in two different ways as $z = x! + y!$, where $x$, $y$ are natural numbers with $0 < x \leq y$? ...
-4
votes
2answers
132 views

How to find all the Quadratic residues modulo $p$

I want to implement Sieve improvement for Fermat's factorization method. For that I need your help answering: How to find all the Quadratic residues modulo $p$? $$\{x ~\vert~ x^2 \equiv q ...