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

learn more… | top users | synonyms

1
vote
3answers
21 views

Problem regarding proving a permutation group

The question states: Show that the set of permutations of three objects form a group. Give the multiplication table for this group. If we take three distinct objects, the set of the ...
-2
votes
0answers
20 views

Prove that there is no $n$ such that $\sigma (n)=9$

Prove that there is no $n\in \mathbb{N}$ such that $\sigma (n)=9$.
1
vote
1answer
31 views

Find the chance that $a^3 + b^3 \equiv 0 (\mod 3)$

We are given set of integer numbers $\{1,2, \dots N\}$. $N \ge 3$ Then perform a drawing with replacement of two elements $a$ and $b$. Problem is to find the probability of following statement holding ...
1
vote
1answer
12 views

Question on Sum of Divisor?

I know $\sigma(m)=24$ for $m=\{14,15,23\}$ but how can we find this numbers? Here is what I did Let the prime factorization of $m$ be $$m=p_1 ^{\alpha _{1}}p_2 ^{\alpha _{2}}\cdot\cdot\cdot p_k ...
5
votes
3answers
43 views

Eisenstein integers and applications to Diophantine equations

Solve the equation $7\times 13\times 19=a^2-ab+b^2$ for integers $a>b>0$. How many are there such solutions $(a,b)$? I know that $a^2-ab+b^2$ is the norm of the Eisentein integer $z=a+b\omega$, ...
-1
votes
3answers
14 views

common solution to $x\equiv 2^{2001}\pmod{4}$ and $x\equiv 14^{2001}\pmod{25}$

How to find the common solution to $x\equiv 2^{2001}\pmod{4}$ and $x\equiv 14^{2001}\pmod{25}$
1
vote
4answers
69 views

Last 2 digits of $\displaystyle 2014^{2001}$

How to find the last 2 digits of $2014^{2001}$? What about the last 2 digits of $9^{(9^{16})}$?
1
vote
0answers
32 views

Proving an identity involving the product of the Möbius function and Euler’s totient function.

Could anyone kindly help me to prove that $$ \sum_{d|n} \mu(d) \varphi(d) = 0 $$ for all even integers $ n \geq 2 $, where $ \mu $ is the Möbius function and $ \varphi $ is Euler’s totient function? ...
1
vote
1answer
33 views

Solving $x^3 + 2x^2 + 5 = 0 \mod 7.$

I'm doing a number theory problem, and I've reduced it to solving $x^3 + 2x^2 + 5 = 0 \mod 7.$ Is there any way to simplify this and solve it in a prettier way than brute force?
0
votes
2answers
32 views

Hexadecimal Representation

Find the last digit of the hexadecimal representation of the number (in decimal notation) $$1+10+10^2+10^3+\cdots+10^{100}$$ I calculated the sum of the series above using GP and obtained ...
0
votes
0answers
16 views
-1
votes
0answers
21 views

How to prove the quadratic reciprocity law? [on hold]

How do you prove the quadratic reciprocity law ? I know Fermat's Little. Does that help ?
2
votes
3answers
41 views

$(a\mod m)/(b\mod m) = (a/b)\mod m$?

b and m are relatively prime (m is prime and $b \in \mathbb Z_m^* $). In truth, I would like to be able to get to the following point (it is a simplified example): $\frac{ab \mod m}{b \mod m} = a ...
0
votes
0answers
13 views

RSA and El Gamal

I was wondering if anyone knew where I could find some examples of encryption with El Gamal and RSA using very large primes? I wrote a code for El Gamal and RSA but I want to test it with some known ...
2
votes
1answer
27 views

Can we tell if a number is prime by the number of its partition ?

Can we tell if a number is prime by the number of its partition ? Or in general, how much can we know about a number itself from its partition function ? I understand that Ramanujan has some ...
1
vote
1answer
26 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
2
votes
0answers
22 views

Which integers are a sum of two relatively prime squares?

It's well known that a positive integer $n$ is a sum of two squares if and only if every prime of the form $4m + 3$ that divides $n$ appears with even multiplicity in the prime factorization of $n$. ...
0
votes
2answers
28 views

If $a \equiv b \bmod n$, then $\gcd(a, n)= \gcd(b,n)$ [duplicate]

Again, I have been stuck in a problem of modular arithmetic. Given that $a,b, n \in \mathbb Z $ and $n>0$ and $a \equiv b \bmod n$. Show that $\gcd(a, n)= \gcd(b,n)$.
-1
votes
0answers
27 views

Define $f : Z/4Z → Z/4Z$ by $f ([a]) = [3a + 1]$.

Define $f : Z/4Z → Z/4Z$ by $f([a]) = [3a + 1]$. (a) Prove that $f$ is a well-defined function. (b) Prove that $f$ is surjective. (c) Prove that $f$ is injective. I'm having trouble with this ...
27
votes
1answer
1k views

Checking a possible proof of Fermat's Last Theorem

Theorem 1.2 of Bennett and Skinner (Canad. J. Math., 2004) asserts that the Diophantine equation $x^{p} - 4y^{p} = z^{2}$ is unsolvable for every prime $p \geq 7.$ The following is a possible proof ...
3
votes
2answers
38 views

GCD Direct Proof

I need to show that if $a,b,c$ are ints such that $\gcd(a,b) = 1$ and $c|(a+b)$, then $\gcd(c,a) = \gcd(c,b) = 1$ I want to try and prove this directly because I think it will be more straightforward ...
0
votes
3answers
44 views

If $\gcd(a,b) = 1,$ then why is the set of invertible elements of $\mathbb Z_{ab}$ isomorphic to that of $\mathbb Z_a\times \mathbb Z_b$?

If $\gcd(a,b) = 1,$ then why is the set of invertible elements of $\mathbb Z_{ab}$ isomorphic to that of $\mathbb Z_a\times \mathbb Z_b$? I know the proof that as rings, $\mathbb Z_{ab}$ is congruent ...
1
vote
0answers
18 views

How to calculate -69^(-1) mod 1313

Which method should I use to calculate $-69^{-1} \mod 1313?$
5
votes
1answer
61 views

Last three digits in number $1^{2013} + 2^{2013} + 3^{2013} + … + 1000^{2013}$

I'm trying to find the last three digits in number $1^{2013} + 2^{2013} + 3^{2013} + ... + 1000^{2013}$. I started by calculating the remainder for even numbers, since I can present even numbers as ...
0
votes
0answers
20 views

Finding set of integer pairs for which two integer polynomials intersect

I am wondering if there is a theorem in number theory that addresses the following issue: Suppose we have two polynomials, f and g, with integer coefficients. Is there a general way to find elements ...
0
votes
1answer
17 views

Show that $\mathbb{Z} [\sqrt p]$ is an ordered Integral Domain.

Let $\mathbb{Z}[\sqrt p]=\{ a+b\sqrt p ~| a,b\in \mathbb{Z},p~is~prime\} $ Assume $\mathbb{Z}[\sqrt p]$ ia an integral domain with usual addition and multiplication. Show $\mathbb{Z}[\sqrt p]$ is an ...
0
votes
3answers
48 views

proof of divisibility of n(n+1)(2n+1) by 6 [duplicate]

How can I prove that $n(n+1)(2n+1)$ (where $n$ is a positive integer) is divisible by 6? As the product is even it is divisible by 2. But I do not know how to prove that it is divisible by 3
1
vote
3answers
55 views

Which rational primes less than 50 are also Gaussian primes?

Which rational primes less than 50 are also Gaussian primes? My attempt: First we need to list all of the rational prime numbers that are less than $50$ ...
1
vote
0answers
17 views

Number of solutions to $x^n \equiv a \pmod{2^b}$.

I've been trying to prove the following statement: Let $m \in \mathbb{N}$ and let $2^k$ be the highest power of 2 that divides $m$. Further, let $a$ be an odd integer such that $x^m \equiv a ...
0
votes
3answers
31 views

if $m>n$ prove that $ a^{2^n} + 1$ is a divisor of $a^{2^m} - 1$

Stuck on this question without much progress. Problem no 49. Section 1.2 Niven. Any hints in the right direction ? For the second part : How can I use this to find $gcd(a^{2^m}+1,a^{2^n}+1)$ ?
1
vote
0answers
23 views

Composite residuosity statement.

Consider the following definition. A number $z$ is said to be $n$-th residue modulo $n^2$ , if there exists a number $y \in \mathbb{Z}_{n^2}^*$ such that $$z\equiv y^n \mod n^2$$ Let us take $n=6$ ...
2
votes
1answer
36 views

Finding the number of divisible integers in the range $[1, 1000]$.

Sorry if this is a stupid question. I am asked to find the number of positive integers in the range $[1, 1000]$ that are divisible by $3$ and $11$ but not $9$. Here's how I $\text{tried}$ to do it. ...
0
votes
2answers
28 views

Show that for any integer not divisible by 2 or 5, there is a multiple of it which is a string of 1s. [duplicate]

Given that a number $n \equiv\{1,3,7,9\} \pmod{10} $ show that there is a multiple of $n$, $q$ that is a string of consectutive $1$s.
2
votes
2answers
86 views

$(a,b)[a,b]=ab$ in non factorial monoids

Do you know of a proof of $[a,b](a,b)=ab$ in $\mathbb Z$ that doesn't use prime factorization? To be more precise let's strip all unnecessary properties and leave only the bare bones of divisibility: ...
0
votes
2answers
19 views

$\gcd(a,n)=d$ and $s,t$ solutions to $ax\equiv b \pmod{n}$ then $s\equiv t\pmod{n/d}.$

If $\gcd(a,n)=d$ and $s,t$ are each solutions to $ax\equiv b\pmod{n}$ then $s\equiv t \pmod{n/d}$. As $d\mid a$ say $a=dm$ and as $s,t$ are each solutions, $as\equiv at\pmod{n}$ so $$a(s-t)=nk ...
0
votes
0answers
19 views

Finding the modular multiplicative inverse using Gauss's Algorithm

I have found that the inverse of 119(mod 261) is 68 by using the extended Euclidean Algorithm. But I cannot find it using Gauss's Algorithm. The fractions seem to cancel out.
2
votes
0answers
35 views

Convergent sum of reciprocals?

Let $n$ denote a positive integer and let $s(n)$ denote the sum of all divisors of $n$, so that $s(n)$ is larger than $n$ (for $n > 1$) but not by much since it's bounded above by $c\ n\log ...
0
votes
0answers
39 views

Prove $2^n \not\equiv 1 \pmod{n}$ for $n>1$ [duplicate]

Prove that $2^n \not\equiv 1 \pmod{n}$ for $n>1$. I'm asking for any advice.
0
votes
1answer
21 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
0
votes
0answers
36 views

Proof of Gauss formula to find number of Primes

How did gauss found this formula to find the number of primes when he was 15 , can anyone provide me the proof.
5
votes
0answers
78 views
+50

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
2
votes
0answers
20 views

Repeated application of interesting function on tuples

This question was inspired by Thursday's CIMC. Suppose you have a function $$f_n: (\Bbb{Z}/n\Bbb{Z})^n\to(\Bbb{Z}/n\Bbb{Z})^n; (a_1,a_2,a_3,\dots,a_n)\mapsto (b_1,b_2,b_3,\dots,b_n)$$ defined as ...
2
votes
3answers
123 views

Prove that $ 2^n \not \equiv 1 \pmod{n} $ for any $n > 1$.

I have proved this in following way. Assume that $ 2^n \equiv 1 \pmod{n} $. that means $n\mid(2^n -1)$. but by proof by contradiction, for $n=3$ this does not hold and we can say $n \nmid (2^n-1) ...
1
vote
0answers
44 views

Does this system of simultaneous Pell equations have any non-trivial positive integer solutions?

Let $a,b,c$ be positive integers satisfying \begin{align} 2a^2-1 &= b^2, \\ 2a^2+1 &= 3c^2. \end{align} The trivial solution is $(a,b,c)=(1,1,1)$. Are there others?
3
votes
3answers
88 views

find the last two digits of $2^{250}$.

Suppose we want the last two digits of $3^{250}$, one can use the theorem $a^{\phi(n)}\cong 1(\mod n)$ whenever $(3,n)=1$. But instead, if i have $2^{250}$, how do i solve this problem, because here ...
0
votes
0answers
23 views

$Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C)\mid D$

I read today that $Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C\mid D$ but I can't find it again, I also can't find any Diophantine equations with 3 variables that doesn't have solutions ...
0
votes
1answer
33 views

An effcient method of solving a Diophantine equation with 3 variables $Ax+By+Cz=D$?

I'm trying to make an efficient algorithm to find one of the solutions and how many solutions there are to the equation $$Ax+By+Cz=D$$ where $A,B,C,D\in \mathbb Z$ and the range for $x,y,z\in \mathbb ...
1
vote
2answers
34 views

Maximum GCD of two polynomials

Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$ I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$. ...
1
vote
2answers
53 views

Find all solutions of the equation $n^m=x^2+py^2$ which satisfy the following properties

Prove or disprove that, There always exists a solution of the equation, $$n^m=x^2+py^2$$ with odd $x$ and $y$ and for all $m\geq k$ for some positive integral $k$. Here $p$ is an odd prime and ...
5
votes
1answer
61 views

How to solve the following equation in $\mathbb{Z}_n$?

Given an $n\in\mathbb{N}$, $a\in \mathbb{Z}_n$ and $x,y\in\mathbb{Z}$, how do I approach to solving the following equation: $a^x \equiv a^y \mod n$ I think that from here I can deduce that: $x ...