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

learn more… | top users | synonyms (1)

0
votes
2answers
39 views

Find $a,b,c$ if $\gcd(a,b,c)=10$ and $\text{lcm}(a,b,c)=100$ [closed]

Find all natural numbers $a,b,c$, so that $\gcd(a,b,c)=10$ and $\text{lcm}(a,b,c)=100$. Any ideas how to approach this problem?
4
votes
3answers
81 views

Find $55! \bmod 61$

I am asked to find the smallest positive $x$ such that $x \equiv 55! \pmod{61}$. This invokes Wilson's theorem where $(p-1)! \equiv -1 \pmod p$. This means $60! \equiv -1 \pmod{61}$. But where to ...
0
votes
3answers
51 views

What is the Euler Totient of Zero?

Wolfram MathWorld defines the Euler Totient function as follows: ...
1
vote
3answers
43 views

Least quadratic nonresidue modulo $p$ is a prime.

Let $p$ be an odd prime. Then, show that the least quadratic nonresidue modulo $p$ is a prime. As a hint is given the fact that Legendre symbol is a homomorphism.
1
vote
0answers
38 views

Prime divisors of $x^2 − 8$

Show that prime divisors of $x^2 − 8$ for odd x must be of the form 8k ± 1. I am momentarily studying the quadratic residues, but I didn't seem to know how to approach this one.
3
votes
2answers
57 views

Proving summations involving the Legendre symbol

In the following, let $(\frac{a}{p})$ denote the Legendre symbol. Then Show that $$\sum _{a=1}^{p-2} \left(\frac{a(a+1)}{p}\right)=-1$$ for an odd prime $p$. I was thinking of factoring out ...
2
votes
0answers
33 views

A question on (odd) perfect numbers

Let $\sigma(x)$ be the (classical) sum of the divisors of $x$. A number $N \in \mathbb{N}$ is called perfect if $\sigma(N)=2N$. An even perfect number $U$ is said to be given in Euclidean form if ...
0
votes
1answer
44 views

number of cubic residues modulo

Determine the number of cubic residues modulo a given squarefree number n. I was given the hint: An integer coprime to n is a cubic residue if $a = u^3$(mod n) for some u.Start from prime ...
0
votes
2answers
77 views

Find 11^644 mod 645 [duplicate]

Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem ...
0
votes
0answers
27 views

The number 0.1234567… is trascendental

The number 0.1234567891011.....whose fractional part is given successively by the sequence of natural integers is trascendental according to a result of Mahler. Can someone help me learn the ...
2
votes
1answer
47 views

Need to solve x^4≡4(mod19)

I need some help in trying to solve : $$x^4\equiv 4\pmod{19}.$$ I have the solution $6$ and $13$ but I'm not clear how it was solved.
1
vote
3answers
39 views

Prove that the greatest common factor of $m+n$ and $m^2+n^2$ is 1 or 2 if $m$ and $n$ are relatively prime.

Prove that the greatest common factor of $m+n$ and $m^2+n^2$ is $1$ or $2$ if $m$ and $n$ are relatively prime natural numbers. Can anyone give a step-by-step answer for this?
0
votes
1answer
20 views

Question on positive integer solutions of $x^4-y^4=z^2$

Suppose the equation $x^4-y^4=z^2$ has solution(s) in positive integers. Then show that the least $x$ value of these solutions is odd. Here is my attempt using contradiction let $x=2k$ $$(2k)^4-y^4 ...
4
votes
1answer
48 views

$A$ is a sum of two postive integer squares?

if $x,y,z,w$ be postive integer,and such $x^2+y^2$ is prime number,and $A=\dfrac{w^2+z^2}{x^2+y^2}\in N^{+}$ show that $A$ is a sum of two postive integer squares? maybe ...
6
votes
1answer
162 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
2
votes
2answers
61 views

Prove $10n^8 - 9n^6 - n^2$ is divisible by $45$

Basically, I have to use Euler theorem to prove that $10n^8 -9n^6 -n^2$ is divisible by $45$ So my approach so far is to say $10n^8 - 9n^6 - n^2 = 0 \bmod 45$ Now $45$ can be factored into $5$ and ...
2
votes
2answers
57 views

Integer solutions of $ y^{2} = 5x^{2} + 17 $

Show that there are no integer solutions to the equation $$y^{2} = 5x^{2} + 17$$ using your knowledge of modular arithmetic and congruence classes. My attempt: Take 17 congruence mod 5 and show that ...
0
votes
2answers
23 views

How to find all primitive triples (a,b,c)? (Pythagorean Triples)

how to find all primitive triples when one value of (a,b,c) is given? For example in this case a = 45. What is the procedure to find the primitive triples ? Conditions for primitive triples are: ...
3
votes
2answers
90 views

Find three integers $x$ so that $271x \equiv 272\pmod{2015}$

I know that $\forall{a,n}\in\mathbb{Z}:\Bigl[\gcd(a,n)=1\Bigr]\implies\Bigl[\exists{k}\in\mathbb{Z}:ak\equiv1\pmod{n}\Bigr]$ In other words, for every pair of co-prime integers $a$ and $n$, there is ...
1
vote
1answer
23 views

Legendre Symbol $\left(\frac4p\right)$ is always congruent to $1$?

Let$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}$ $\leg ap$ denote the Legendre symbol. In all cases $a=4$. and $p$ takes values of different odd prime numbers $p$. For $p=5$: $\leg 45$ -> ...
1
vote
1answer
16 views

Prove that $(s-1)!(p-s)!\equiv(-1)^s \pmod p$

A problem asks me to prove: Prove that for $0<s<p$, $$ (s-1)!(p-s)! \equiv (-1)^s \pmod p. $$ Wilson's theorem states that $(p-1)! \equiv -1 \pmod p$. I really have no idea where to ...
1
vote
3answers
31 views

Prove that if $a$ and $a-1$ are relatively prime to $n$ then $1+a+a^2+\cdots+a^{\varphi(n)-1}\equiv 0 \pmod n$

I think I'm off to the right start where I applied Euler's Theorem and got: $$a^{\varphi(n)}-(a-1)^{\varphi(n)}\equiv 0 \pmod n. $$ But I'm not sure how to proceed or if I have the right idea.
3
votes
3answers
42 views

If $p>3$ what are two solutions of $x^2 ≡ 4 \pmod p$?

Theorem used: "Suppose that $p$ is an odd prime. If $p \nmid a$, then $x^2 ≡ a \pmod p$ has exactly two solutions or no solutions." Question: If $p>3$ what are two solutions of $x^2 ≡ 4 \pmod p$? ...
1
vote
2answers
82 views

Find all n such that $\phi(\phi(n)) = 1$

Find all n such that $\phi(\phi(n)) = 1$. I was thinking of firstly writing $\phi(n) = n\prod_{p|n} {1-1/p}$ and then again but I couldn't find a result.
6
votes
2answers
84 views

Prove that $\forall n > 1 \quad2^n - 1 \pmod n \neq 0$

Prove that $\forall n > 1, \quad2^n - 1 \pmod n \neq 0$ I've thought of the induction but I can't figure out how to prove the step. Fermat's theorem (and its variations) aren't particularly useful ...
0
votes
0answers
32 views

Existence of non-coprime between an integer and an arithmetic sequence

Take two relatively prime numbers $m,n \in \mathbb{Z}$ (i.e. $gcd(m,n) = 1$) where $m \neq 1$. Show that: $$\forall a \in \mathbb{Z} \textrm{ s.t. } 0<a<n$$ $$\exists i \in \mathbb{Z^+} ...
2
votes
1answer
50 views

$\phi(n)/n$ is minimal

I am working on a number theory exam and this question seems quite interesting. How do I really approach it? Determine the element $n_k$ of the set {$n \in N: w(n)=k$} for which $\phi(n)/n$ is ...
0
votes
1answer
41 views

Express the following in terms of $\phi$

1. Express $\phi (n^k) $ in terms of n and $\phi(n)$. I know the result is supposed to be $ n^{k-1} \phi(n)$ and I was thinking of approaching it by induction but I am not quite sure. 2. Given $ m ...
1
vote
2answers
26 views

Number of reduced fractions in terms of Euler's totient function

Find the number of reduced fractions $\frac{a}{b}$ with $1 \le a < b \le n$ in terms of Euler's totient function. I was thinking that is should be of the form $\phi(1) + \phi(2) + \ldots + ...
3
votes
2answers
54 views

Is fibonacci sequence a member of more broad family of sequences?

Yesterday, I was pondering on the Fibonacci sequence and I started to discover some features of it that were previously unknown to me. Such as, 1, 1, 2, 3, 5, 8, 13, 21, 34 .... 1 ) The nth element ...
3
votes
2answers
35 views

Find $n$ such that $(m-1)(m+3)(m-4)(m-8)+n$ is a perfect square for all $m$

Find $n$ such that $(m-1)(m+3)(m-4)(m-8)+n$ is a perfect square for all $m$ I am thinking of starting like this $(m-1)(m+3)(m-4)(m-8)+n = k^2 \implies (m-1)(m+3)(m-4)(m-8) = k^2-n$ Honestly ...
-1
votes
0answers
595 views

$ (x+y) \geq (p_n +2) $?

I recently worked on a previous idea of mine (a prime number inequality, which I had posted in this community but didn't know Latex then and couldn't discuss it's proof). I was wondering how powerful ...
0
votes
2answers
41 views

Finding order of an integer with (mod 9)?

I am trying to solve a problem to find the order of some integers with (mod 9). I understand the concept I also have the solution to the problem. My calculations are also correct except for a few ...
0
votes
1answer
37 views

Suppose that $p$ is prime. If $a$ and $b$ are integers for which $a^p \equiv b^p \pmod{p}$, then how do I prove that $a \equiv b \pmod{p}$.

I saw the explanation of it here using Fermat's Little Theorem but I do not get how I can go from $a^p \equiv a \equiv b^p \equiv b \pmod{p}$ because of transitivity (I guess I want to ask what is ...
2
votes
8answers
1k views

When is a number even?

Why does something like $a^2 = 2b^2$, show that $a^2$ and thus $a$ are even numbers? My feeling is that it's because one can divide $a^2$ by two and hence it must be even. Can anybody give me a ...
1
vote
2answers
27 views

Let $k = (a+b,a^2+b^2-ab)$. If $(a,b)=1$ then $k = 1$ or $k=3$.

Yes, I know that this questions has two answers, but I can't see why $k$ can't be 27, or any other $3^n$ with $n \neq 2$.
0
votes
2answers
68 views

Find j,k such that $2^j + 3 = 7^k$

Find all $j,k$ such that $2^j + 3 = 7^k$. I think that the only solution is $j=2$. Because of the exponential growth of $2$ and $7$. But I am not that sure.
4
votes
2answers
69 views

Show the following if $p$ is prime

If $p$ is prime and $ a \ge 2$, prove that $$ d = (a - 1, \frac{a^p - 1}{a - 1}) = \begin{cases} p & \text{if } p \mid (a - 1)\\ 1 & \text{if } p \nmid (a - 1) \, . \end{cases} $$ I was ...
-3
votes
1answer
67 views

Elementary Number Theory

Let '$a$' be an integer and '$n$' a positive integer. Prove or provide a counter example to each of the following three statements. If $a\equiv \pm 1 \pmod{p}$ for all primes '$p$' dividing $n$, ...
0
votes
3answers
40 views

Find all the positive natural solutions of $x^2+y^2=3z^2$. [duplicate]

Find all the positive natural solutions of $x^2+y^2=3z^2$. I guess it has something to do with Pythagorean triples, but I don't know how to relate it properly. Suggestions, hints, or any sort of ...
0
votes
0answers
25 views

$j$-volume of $j$ dimensional parallelepiped inside $\mathbb{R}^n$

Let $v_1, ..., v_j \in \mathbb{R}^n$ be linearly independent. Let $V = \mathbb{R}v_1 + ... + \mathbb{R} v_j$ be a subspace of $\mathbb{R}^n$ and $\Gamma = \mathbb{Z}v_1 + ... + \mathbb{Z} v_j$ a ...
2
votes
2answers
40 views

Prove that if $\gcd(m,n)=1$ then every divisor $d|mn$ has a unique form $d=ab$ such that $a|n$ and $b|m$.

I can see why this is true. I have a problem with formality or with explaining certain things properly. An attempt: suppose there are two forms $d=a_na_m=b_nb_m$ such that $a_n,b_n|n,a_m,b_m|m$ but ...
2
votes
1answer
55 views

Number Theory : Show that $\sigma(n)$ $=$ $2n$ for $n$ $=$ $(2^{m-1})$ $(2^{m} -1)$

I was working through some basic Number Theory Problems when I came across : Given an integer $m$ $≥ 2$ such that $(2^{m} -1)$ is a prime, and $n$ $=$ $(2^{m-1})$$(2^{m} -1)$, then show that ...
2
votes
3answers
78 views

Number Theory : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$

I was working my way through some basic Number Theory Problems , when I came across : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$ , where $\phi(x)$ is the euler phi function I am ...
5
votes
3answers
83 views

Why can $5^{2n+3} + 3^{n+3} \cdot 2^{n} \quad \forall n \in \mathbb{N}$ never be a prime number?

It seems to be true for the first thousand $n$ but I really can't think of a way to prove this statement. Any kind of help will be appreciated!
2
votes
1answer
82 views

A generalization of Goldbach's conjecture?

In a previous question I asked about a counterexample for an observation I did about the Goldbach's comet: it seems that there is always common prime shared between the Goldbach's prime pairs of the ...
4
votes
6answers
110 views

Proof that $a+\frac{1}{a}\in\mathbb{Z}$ iff $a=\pm1$

I showed someone how to prove by induction that if $a+\frac{1}{a}\in\mathbb{Z}$ then also $a^n+\frac{1}{a^n}\in\mathbb{Z}$. He noted that there was no need for induction since obviously ...
6
votes
1answer
89 views

Proving $\,2\sqrt 2 + 1\,$ is irrational by contradiction

I am working on some review questions for my Discrete Structures final and I needed some assistance for the problem "Prove by contradiction that $\,2\sqrt 2 +1$ is irrational". Now I know how prove ...
4
votes
1answer
51 views

A question about Euler's totient function

Prove that for every natural number $m$, there exists a natural number $n$ such that $$\phi(n)=\phi(n+m)$$ For odd numbers $m$, we can choose $n=m$ and use the identity $\phi(2m)=\phi(m)$.
6
votes
1answer
100 views

The totient of Fibonacci numbers is divisible by $4$

Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient ...