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

learn more… | top users | synonyms (1)

0
votes
0answers
25 views

How do you evaluate the quadratic residue of 7 mod p?

How do you evaluate this quadratic residue? I've been playing around with some specific values and I suspect 1 if p is of the form 28k+/-1, 3, 9 and -1 if 28k+/- 5, 11, 13. I have no idea how to come ...
1
vote
1answer
24 views

For what maximum positive $k$ is $2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$ true?

I am trying to find the maximum value of $k$ such that the inequality $$2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$$ is satisfied. I impose restrictions that $n \in \mathbb{Z}$ with $n \geq ...
6
votes
3answers
261 views

Solution to exponential congruence

Is there a clever solution to the congruence without going through all the values of x up to 58?$$2^x \equiv 43\pmod{59}$$ Can I somehow use the fact that $2^4 \equiv -43\pmod{59}$ ?
5
votes
1answer
70 views

The number of zeros in the expansion of $n!$ in base $12$

During an interview last year I was asked the following question: How many zeros appear at the end of $n!$ in base $12$, where $n$ is a positive integer? I applied the known Legendre formula for ...
2
votes
1answer
15 views

How to find the highest [natural] radix base of a given number with a natural output

Like the title says, I'm trying to make a program that finds the highest natural radix of a given number with a natural output. My program works, but it loops every number possible number up to a ...
1
vote
3answers
63 views

What does x equivalent to 2 mod 15 mean?

I came across the following question: Consider the following system of equivalences of integers. $$ x \equiv 2 \bmod{15} $$ $$ x \equiv 4 \bmod{21} $$ The number of solutions in $x$, where $1\le ...
0
votes
2answers
75 views

Find the smallest number which leaves remainder $8,12$ when divided by $28$ and $32$.

The question is- Find the smallest number which leaves remainder $8,12$ when divided by $28$ and $32$. My book gives directly a formula- Required number=Lcm(the two numbers;here 28 and ...
7
votes
2answers
102 views

Show that $x^2 + y^2$ and $x^2 - y^2$ cannot both be perfect squares at the same time where $x, y \in \mathbb{Z}^+$.

Show that $x^2 + y^2$ and $x^2 - y^2$ cannot both be perfect squares at the same time where $x, y \in \mathbb{Z}^+$. I think that $x^2 + 2xy + y^2$ and $x^2 + y^2$ are not consecutive squares ...
1
vote
0answers
46 views

Defining Logic Algebraically, Math Functions & Integers

Introduction I wanted to define some functions algebraically to be used as "logical conditions" that would be assigned to a term $t$ to "control" its value. Or in some other words, I wanted to ...
0
votes
1answer
21 views

Problem on coprimality testing.

If we have integers $a,b,c$ with $gcd(a,b)=1$ and $0<a,b<c$ then for what $x,y$ with $0<a,b<x,y<c$ we $$\gcd(ac-bx,bc-ay)=1$$ hold and for what such $x,y$ we have ...
2
votes
3answers
71 views

Finding a number $n$ and $k$ such that $nx+k$ will be a perfect square for any two given $x$.

Given two positive integers $x_1,x_2$, is it always possible to find positive integers $n$ and $k$ such that the expression $nx_i+k$ becomes a perfect square for each $i$ ?
1
vote
3answers
68 views

Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$

Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$ Let $d=\gcd(4n^2+1,24)$ then we have: $$d|24n^2+6,24n^2\ \Rightarrow\ d|6\ \Rightarrow\ d|6n^2,4n^2+1\ \Rightarrow\ d|12n^2,12n^2+3\ ...
8
votes
2answers
110 views

If $\varphi(x) = m$ has exactly two solutions is it possible that both solutions are even?

If $\varphi(x) = m$ has exactly two solutions is it possible that both solutions are even? Here, $\varphi(x)$ is Euler's phi function, the number of positive integers less than or equal to $x$ ...
4
votes
1answer
40 views

Proving that $y$ is a square mod $p$ and $-y$ is square mod $q$

Given that $p, q \equiv 3 \pmod 4$, neither $y$ nor $-y$ has a square root mod $pq$, and that $y$ is invertible mod $pq$, how would I prove that $y$ is a square mod one of $p, q$ and $-y$ is a square ...
0
votes
2answers
35 views

GCD divisibility of LCM

Show that the following conditions are equivalent: i) There exist positive integers $a,b$ such that $\gcd(a,b)=d$ and $\operatorname{lcm}(a,b)=m$. ii) $d∣m$ The first direction is very ...
2
votes
0answers
21 views

What triples of square-free integers $(r,s,t)$ admit integer solutions $(x,y,z)$ where $rx^2,sy^2,tz^2$ are consecutive integers?

In this post on the consecutive integers $b^2,2a^2,3c^2$, I asked whether the trivial solution $a=b=c=1$ was the only one. At this time, that question appears to have been answered in the affirmative ...
1
vote
3answers
60 views

If $a\mid b^2$ and $\gcd(a,b) = 1$, how can I prove that $a\mid b$? [duplicate]

Let $a$, $b$ be positive integers. Clearly if $a\mid b^2$, $ak = b*b$ for some $k$ in $\mathbb{Z}$. Intuitively, $a$ will be the gcd so it must be $1$. But how can I show this? Is there a more ...
0
votes
1answer
24 views

Let $a,b \in \mathbb{Z}$. Prove that if $b = qa + r, q,r \in \mathbb{Z}$, then $gcd(a,b) = gcd(r,a)$ [closed]

This is a lemma from Rotman's book "Advanced Modern Algebra" Let $a$ and $b$ be integers(and so are $q$ and $r$). I need to prove that if $b = qa + r$, then $gcd(a,b) = gcd(r,a)$. Not sure how to ...
13
votes
1answer
129 views

$2^n + 3^n = x^p$ has no solutions over the natural numbers

A few weeks ago, I was asked to prove that $2^n + 3^n = x^2$ has no solutions over the positive integers. My proof was: $2^n + 3^n \equiv (-1)^n \equiv \pm 1 \mod{3}\\\text{However, quadratic residue ...
0
votes
1answer
13 views

Prove that multiplication by an integer $a$ that is relatively prime to $n$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself

If gcd$(a,n)=1$, then multiplication by $a$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself. My working: If $n=p$ a prime, then we can use the Fermat's Little Theorem. If $n$ is not prime in ...
2
votes
1answer
58 views

Are primes less than the sum of divisors?

I am trying to prove that Let $p_n$ be the $n$th prime number, $\sigma (n)=\sum_{d|n}d$. Prove that $$\sigma(n) \le p_n$$ It seems obvious at first glance-to me, at least the sum of divisors of ...
5
votes
2answers
38 views

For any $a$ in $\Bbb Z$, prove that $6|a(a+5)(a+10)$

So I am given this question for my number theory and proof class: For any $a \in \Bbb Z$, prove that $6|a(a+5)(a+10)$. I've thought about a few different ways to approach this. I think I could ...
1
vote
1answer
38 views

Solve $\lfloor x \rfloor = ax+1$ for integral $a$

Solve $\lfloor x \rfloor = ax+1$, where $a$ is an integer. I have found the values of $x$ for $a=0$, $a=1$ and $a=-1$. But I don't know how to continue. How can I find the solutions for integral ...
1
vote
0answers
32 views

Infinitely many primes of the form $16n+1$? [duplicate]

As the title states I need to prove there are infinitely primes of the form $16n+1$ but I have absolutely no idea how to do it.
1
vote
2answers
23 views

Help me to understand question on Linear Congruence in simplest and elaborated way.

I came across the following congruence in which I have to get value of $x$. They devide it by $3$ which I understand how and multiply it by $7$ on both sides and proceeds further as shown by photo ...
0
votes
1answer
45 views

Exponentiation on the natural numbers. Prove the identities $n^{(m+k)}=n^m \cdot n^k$ and $n^{(m \cdot k)}=(n^m)^k$.

Moschovakis, Set theory, Chapter 5, Problem, x.5.3. Exponentiation on the natural numbers is defined by the following recursion on $m$: $n^0=1$, $n^{Sm}=n^m \cdot n.$ Show that it satisfies the ...
4
votes
1answer
53 views

Solving the Diophantine Equation $x^2 - y! = 2001$ and $x^2 - y! = 2016$

I had recently faced a problem: Solve the Diophantine Equation $x^2 - y! = 2001$. Solving it was quite easy. You show how $\forall y \ge 6$, $9|y!$ and since $3$ divides the RHS, it must divide ...
7
votes
1answer
101 views

how to calculate double sum of GCD(i,j)?

I stumbled upon a programming question which wanted me to calculate : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ now I wrote a code to solve this problem but it takes polynomial time to ...
-1
votes
0answers
22 views

If t divides the LCM of two non-zero integers, then the two integers divides t

Suppose that $k=LCM\left ( m,n \right ) \exists k \in \mathbb{Z} \forall m,n \in \mathbb{Z}$ and $\space t \mid k$ $\exists t \in \mathbb{Z}$ , Then, both m and n must divides t. Is the ...
0
votes
3answers
45 views

How many numbers less than 100 have the sum of factors as odd?

How many numbers less than 100 have the sum of factors as odd? Answer is 16 This question and explanation is taken from careerbless.com The link given derives the answer using some ...
1
vote
1answer
19 views

For any integers $a,b$ the relatively prime integers $m,n$ giving $am + bn = 0$ are unique.

I can prove for any integers $a,b$ that a choice of relatively prime $(m,n)$ gives $am + bn = 0$: 1) Set $m$ to $-b$ 2) Set $n$ to $a$ 3) Divide $m$ and $n$ by $d = gcd(a,b)$. 4) $m$ and $n$ are ...
0
votes
1answer
30 views

Find the smallest number of toys that person had

A person had a number of toys to distribute among children . At first he gave $2$ toys to each child , then $4$ , then $5$ ,and then $6$ , but was always left with one . But if he had given $7$ toys ...
0
votes
1answer
52 views

How do I prove 'For all integers a, there exists an integer b so that 3|a+b and 3|2a+b?

My approach is to divide the prove into 2 cases, where case1 is when its just 'a' and case 2 is when it is '2a'. Is that any close to being the correct proof?
1
vote
1answer
22 views

Constant angles and powers

One can verify without difficulty that for all triple $(a,b,c)$ of real numbers greater than $1$, with $a\le b\le c$, and for all positive integer $n$, the equality $$a^n+b^n=c^n\qquad (*)$$ ►it has ...
1
vote
2answers
29 views

Help me prove a modular congruence!

Show that $a^{42} \equiv 1 \pmod{1764}$ if $\gcd (a, 1764) = 1$. Use Euler's theorem. Hint: $1764 = 4 \cdot 9 \cdot 49$ Hint: if t is a common multiple of $\phi(m)$ and $\phi(n)$, where ...
3
votes
1answer
37 views

Solve this problem on functions

Let $f$ be a bijection from the set of non-negative integers to itself. Show that there exist integers $a$,$b$,$c$ such that $a < b < c$ and $f(a)+f(c)=2f(b)$. I don't know how to approach ...
5
votes
3answers
87 views

Proving that the only integer solution of $2x^2+3y^2=z^2$ is $(0,0,0)$

I'd like to prove that the only integer solutions of $$2x^2+3y^2=z^2$$ is $(0,0,0)$. By working in $\mathbb{Z}_2$ and $\mathbb{Z_3}$, I have gone as far as proving that in $\mathbb{Z}$, any integer ...
0
votes
0answers
17 views

Prove that among five consecutive positive integers… [duplicate]

Prove that among five consecutive positive integers there is one integer which is relatively prime to the other four. I tried assuming that it is false and then find a contradiction, but that din't ...
4
votes
3answers
47 views

Sum of number-of-divisors function equals $\sum_{j=1}^{n} \lfloor n/j \rfloor$.

I am trying to prove the identity $$t(1) + t(2) + \cdots + t(n) = \Big\lfloor \dfrac{n}{1} \Big\rfloor + \Big\lfloor \dfrac{n}{2} \Big\rfloor + \cdots + \Big\lfloor \dfrac{n}{n} \Big\rfloor,$$ where ...
0
votes
1answer
25 views

Infinitude of primes in logical notation [closed]

Can this formal statement about the infinitude of primes be improved (i.e. made shorter and/or more elegant and standard)? $$\#\left \{ m\in \mathbb{N } \backslash\left \{ 1 \right \} : \exists n ...
4
votes
2answers
106 views

Without using prime factorization, find a prime factor of $\frac{(3^{41} -1)}{2}$

Not sure how to go about this. Law of quadratic reciprocity and Euler's Criterion is recently learned material but I'm not sure how this applies.
2
votes
3answers
276 views

Proof using deductive reasoning

I need to deductively prove that the sum of cubes of $3$ consecutive natural numbers is divisible by $9$. I can prove deductively that they are divisible by $3$ but so far any combination I choose ...
2
votes
0answers
34 views

Is there anyway to find how many prime factors has a composite number without knowing them?

Let's call f(n) the function that gives us the number of different prime factors of a composite number n For example: f(24)=2 Let's call g(n) the function that gives us the number of prime factors of ...
4
votes
2answers
34 views

Primes of the form $(2p)^{2}+1$, $p$ prime, have $h^{2}+1$ as a prime divisor?

I'm an undergraduate student and I usually ask questions here about things I'm struggling with in my academical mathematical studies, but this particular question is actually more like a curiosity. ...
1
vote
1answer
21 views

divisibility theorem proof?

I have found in a book the proof for the divisibility problem that says: If $a$ and $b$ are integers and $b$ is not equal to zero, then there is a unique pair of integers $q$ and $r$ such that ...
3
votes
1answer
120 views

For which polynomials $f$ is the subset {$f(x):x∈ℤ$} of $ℤ$ closed under multiplication?

You surely know about the Brahmagupta–Fibonacci identity, $$(a_1^2 + b_1^2)(a_2^2 + b_2^2) = (a_1a_2 \pm b_1b_2)^2 + (a_1b_2 \mp a_2b_1)^2$$ which tells us that the product of two numbers, each of ...
0
votes
0answers
20 views

Pythagorean Triples $\mod{c}$

I have a quick question regarding modular arithmetic. If I have a Pythagorean Triple $(a, b, c)$, is it possible to consider this equation $\mod{c}$. That is to say, Is the implication $$a^2 ...
1
vote
0answers
14 views

computing difference between all pairs of numbers which is given in ascending order

What are the different ways with which we can compute difference between all pairs of numbers among given numbers in ascending order. Say we have x1,x2,x3.....x8 where X1 X2..X8 ARE IN ASCENDING ...
1
vote
1answer
18 views

Proof of $\sum_{j=1}^{p-1} \lfloor jq/p \rfloor = \frac{1}{2}(q-1)(p-1)$ Involving Pairing of Summands

I've seen the proof of the identity $$\sum_{j=1}^{p-1} \lfloor jq/p \rfloor = \frac{1}{2}(q-1)(p-1)$$ where $p$ and $q$ are coprime positive integers. This involves counting the remainders ...
1
vote
0answers
26 views

Squares in a second order linear recurrence of positive integers

Let the integer sequence $n_k$, ($k\ge 0$) be defined as $$ n_0=1$$ $$n_1=64$$ $$ n_k=38 n_{k-1}-n_{k-2}-90$$ How can one find the squares in such a sequence? Besides $ n_0=1^2, n_1=8^2$, we also ...