Tagged Questions

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

204 views

complete residue system modulo $p$

if $p$ is odd prime and $\{a_1,...,a_p\},\{b_1,...,b_p\}$ are complete residue system modulo $p$ how to prove $\{a_1b_1,...,a_pb_p\}$ is not complete residue system modulo $p$. complete residue ...
360 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
103 views

How do I show that $6(4^n-1)$ is a multiple of $9$ for all $n\in \mathbb{N}$?

How do I show that $6(4^n-1)$ is a multiple of $9$ for all $n\in \mathbb{N}$? I'm not so keen on divisibility tricks. Any help is appreciated.
92 views

How to find $\gcd(a^{2^m}+1,a^{2^n}+1)$ when $m \neq n$?

How to prove the following equality? For $m\neq n$, $\gcd(a^{2^m}+1,a^{2^n}+1) = 1$ if $a$ is an even number $\gcd(a^{2^m}+1,a^{2^n}+1) = 2$ if $a$ is an odd number Thanks in advance.
291 views

Finding solutions of the system $27x + 90 \equiv 18 \pmod{99}$

I have to find solutions for the expression $$27x + 90 \equiv 18 \pmod{99}$$ My only problem is that I can only solve expressions like $ax \equiv b \pmod{n}$. How can I get rid of the $90$? ...
186 views

Prove that if $g$ is a primitive root of $n$ and $g*b \equiv 1 \pmod n$, then $b$ is also a primitive root of $n$.

Some useful facts I am trying to use: If the multiplicative group $U_n$ modulo $n$ is a cyclic group, a generator $g$ of $U_n$ is called a primitive root of $n$. if $g$ in $U_n$ is a primitive root,...
194 views

Proof involving modulus and CRT

Let m,n be natural numbers where gcd(m,n) = 1. Suppose x is an integer which satisfies x ≡ m (mod n) x ≡ n (mod m) Prove that x ≡ m+n (mod mn). I know that since gcd(m,n)=1 means they are ...
110 views

I have exams on number theory coming up.And this is something I don´t really understand, how to handle such tasks. Could anyone please explain it to me in a very understandable way (just studying ...
3k views

How to find all the primitive roots in $\mathbb{Z}/49\mathbb{Z}$.

I need to find all the primitive roots of 49. First note, $ϕ(49) = 42$ Is there an easier way to go about trying all numbers less than $42$ to find the primitive roots of $49$ if we already know ...
116 views

$\forall n \in \Bbb N , 18\mid1^n+2^n+\ldots+9^n-3(1+6^n+8^n)$

How to prove:$\forall n \in \Bbb N , 18\mid1^n+2^n+\ldots+9^n-3(1+6^n+8^n)$ ?
105 views

a problem in elementary number theory :$n=a+b$

how to prove if $n\in \Bbb N$and $n\gt 6$ then there exists $a,b \in \Bbb N$ such that $a,b\ge 2$ and $\gcd(a,b)=1$ and $n=a+b$. Thanks in advance.
192 views

Don't understand casting out nines

Let n be a positive integer. If the sum of the digits of n is divisible by 9, then n is divisible by 9. I got upto here, ...
236 views

Show that $2^{341}\equiv2\pmod{341}$

Show that $2^{341}\equiv2\pmod{341}$ My work: Prime factorization of $341 = 31\cdot11$, thus $2^{11\cdot31}\equiv2\pmod{31\cdot11}$ $2^{341} = 2=2(2^{340}-1)$, we have $2^{340}\equiv1\pmod{341}$ ...
1k views

How to prove that a six-digit number of the form $abcabc$ is divisible by 3 distinct primes

$a,b,c \in \{0,1,2,\ldots,9\}$ with at least one of $a$, $b$, $c$ nonzero. Prove that the six-digit integer $abcabc$ is divisble by at least 3 distinct primes. I received an answer from the back of ...
64 views

86 views

239 views

find the minimum value of $a+b+c$

There are natural numbers: $a$, $b$, $c$. $$\begin{cases} ab+bc+ca+\frac32(a+b+c)=5015,\\ 2abc-a-b-c=6366 \end{cases}$$ I need to find the minimum value of $a+b+c$. To my mind there's ...
320 views

Is every Mersenne prime of the form : $x^2+3 \cdot y^2$?

How to prove or disprove following statement : Conjecture : Every Mersenne prime number can be uniquely written in the form : $x^2+3 \cdot y^2$ , where $\gcd(x,y)=1$ and $x,y \geq 0$ ...
3k views

How to compute modular square roots when modulus is non-prime

I am trying to implement James McKee's speed-up of Fermat's factoring algorithm described at http://www.ams.org/journals/mcom/1999-68-228/S0025-5718-99-01133-3/home.html. The algorithm factors semi-...
252 views

Maximum number of square roots of $a \in \mathbb{Z}_n$

What is the maximum number of square roots an element of $\mathbb{Z}_n$ can have?
154 views

Prove a property of divisor function

Let $n$ be a positive natural number whose prime factorization is $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_i$ are natural distinct prime numbers, and $a_i$ are positive natural numbers. ...
302 views

What is an example of positive integer that cannot be written as $p+a^2$, with $p$ prime or 1 and $a \geq 0$?

What is an example of positive integer that cannot be written as $p+a^2$, with $p$ prime or 1 and $a \geq 0$? This should be simple, but every example I've come up with so far seems to satisfy the ...
222 views

A number system

Can we have a number system $S$ of cardinality continuum such that for every $x \in S$, there is a unique $y \in S$, such that for all $z>x$ in S, $x<y\le z$ holds?
Let $a$, $b$, $c \in \mathbb{N}$. $[a, b]$ denotes $\mathrm{lcm}(a, b)$ and $(a,b)$ denotes $\gcd(a, b)$ Show that $(a,[b,c]) = [(a,b),(a,c)]$. $[a,(b,c)] = ([a,b],[a,c])$.
show that $\gcd(a_1, \dots, a_n) = \gcd(a_1, \dots, a_{n-2},\gcd(a_{n-1},a_n))$
Let $a_1, \dots, a_n \in \mathbb Z$ such that $a_{i_0} \neq 0$ for some $i_0 \in \{1, \dots, n\}$. How to show that $\gcd(a_1, \dots, a_n) = \gcd(a_1, \dots, a_{n-2},\gcd(a_{n-1},a_n))$. (Hint: show ...