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

learn more… | top users | synonyms (1)

2
votes
0answers
112 views

Is $\dfrac{\cos\theta}{\sqrt{15}}$ irrational? [on hold]

In general I was wondering if $\cos\theta$ was between $0$ and $1$ exclusive then would $\dfrac{\cos\theta}{\sqrt{15}}$ be irrational? And just on another note is an irrational times a transcendental ...
0
votes
1answer
45 views

If $\ (1+3x+x^2)^{10}=\sum_{r=0}^{20}a_r x^r\ $ then…

If $$\ (1+3x+x^2)^{10}=\sum_{r=0}^{20}a_r x^r\ $$ Then then what is the least number except 1 which divides the following:$$\ \sum_{r=0}^{20}(3r+1)a_r\ $$ EDIT: i have put x=1 then it is something ...
1
vote
1answer
22 views

$2^i \equiv 2^j \pmod n$ implies $2^{j−i }\equiv1$ if $n$ is odd; also if $n$ is even?

Show that, if $0 \leq i < j$ and $2^i \equiv 2^j \pmod n$ and $n$ is odd then $2^{j−i} \equiv 1 \pmod n$. Is this necessarily true if $n$ is even? I have tried to prove this by using Fermat's ...
-1
votes
0answers
23 views

Find the unit digit of this expression [on hold]

What is the unit digit of the expression $\large33^{34^{35^{36\dots\infty}}}$. $(A)\quad 3,\qquad (B)\quad 4,\qquad (C)\quad5, \qquad(D)\quad9$
1
vote
1answer
37 views

Is number $1$ the only natural number with this property?

Let us call a number $b \in \mathbb N$ gcd-friendly if there exists $n_0(b) \in \mathbb N$ and $a_0(b) \in \mathbb N$ such that for every $n \geq n_0(b)$ and $a \geq a_0(b)$ we have $\gcd ...
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
251 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
68 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
59 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 ...
-2
votes
0answers
18 views

How to make proof with cassini formula? [closed]

Let Fn, n. Fibonacci number and n even. 4t+1 is one divisor of Fn.( t, factor of Integer Numbers). How to make it's proof with Cassini formula)
0
votes
2answers
61 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 ...
6
votes
2answers
97 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
45 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
20 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
66 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
108 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
39 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
34 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
22 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)$

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
123 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
52 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
36 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
31 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
52 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
99 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
43 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
36 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
86 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
16 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
46 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
101 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
275 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
33 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
33 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. ...