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

learn more… | top users | synonyms (1)

2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
4answers
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.
2
votes
3answers
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.
2
votes
5answers
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$? ...
2
votes
3answers
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,...
2
votes
3answers
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 ...
2
votes
3answers
110 views

Task on divisibility

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 ...
2
votes
3answers
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 ...
2
votes
2answers
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)$ ?
2
votes
2answers
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.
2
votes
1answer
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, ...
2
votes
1answer
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}$ ...
2
votes
1answer
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 ...
2
votes
5answers
64 views

Showing $na \equiv 1 \pmod m$ and $n'a \equiv 1 \pmod m \implies n \equiv n' \pmod m$ for $(a,m) = 1$

We have $(a,m) = 1$ iff exists integer $n$ such that $na \equiv 1 \pmod m$. Prove $na \equiv 1 \pmod m$ and $n'a \equiv 1 \pmod m$ implies $n \equiv n' \pmod m$. For this question, I have so far $na ...
2
votes
4answers
101 views

modular arithmetic (number theory)

Assume that $$7^{64} = 1 \mod 120.$$ I am trying to find $$7^{62} \mod 120.$$ In my maths text, I was told that: $$\begin{align} 7^{62} & = 7^{64} \cdot 7^{-2} \\ & = 7^{-2} \quad \\ &= ...
2
votes
2answers
335 views

Finding the smallest positive integer $N$ such that there are $25$ integers $x$ with $2 \leq \frac{N}{x} \leq 5$

Find the smallest positive integer $N$ such that there are exactly $25$ integers $x$ satisfying $2 \leq \frac{N}{x} \leq 5$.
2
votes
3answers
108 views

Quadratic Residues Are Distinct

I'm having a little trouble understanding the proof that the quadratic residues mod p, given by: $1^2,2^2,...,(\frac{p-1}{2})^2$ are distinct. So far I have this: If we have $j$ such that $\frac{p-...
2
votes
2answers
132 views

Basic Modular Exponentiation reasoning

I am trying to understand the modular exponentiation algorithm. Why is it that: $x^2 \mod5 = (x\mod5)(x\mod5) \mod 5$ What is the basic reasoning behind this?
2
votes
3answers
85 views

Suppose that we have $a=p_1 \cdot p_2\cdot p_3=q_1\cdot q_2\cdots q_s$ where $p_1,p_2,p_3$ and $q_1,q_2,…,q_s$ are primes. Explain why $s=3$.

Suppose that we have $a=p_1 \cdot p_2\cdot p_3=q_1\cdot q_2\cdots q_s$ where $p_1,p_2,p_3$ and $q_1,q_2,...,q_s$ are primes. Explain why $s=3$. This seems like a pointless question, but is it $3$ ...
2
votes
3answers
374 views

Inverse number and linear congruence

Find all integer between 1 to 30 that have inverse modulo 30 and for each one find its inverse. Well, I think there are 8 number that have inverse modulo 30: $1,7,11,13,17,19,23,29$. I guess the ...
2
votes
2answers
136 views

A question about rational.

Is that true : Every positive rational number $q$ can be written as $q = \sum_{i=0}^{k}1/n_i$ , where $n_i,k$ are positive intergers and $n_i\not=n_j$ if $i\not=j$.
2
votes
1answer
241 views

Better representaion of natural numbers as sets?

Natural numbers can be represented as $0=\emptyset$ $1=\{\emptyset\}$ $2=\{\{\emptyset\}\}$ $...$ or as $0=\emptyset$ $1=\{0\}=0\cup\{0\}$ $2=\{0,1\}=1\cup\{1\}$ $...$ What are the names of ...
2
votes
3answers
353 views

Primitive root modulo p

Let $p$ be an odd prime with a primitive root $g$. Prove that $$\prod_{x=1}^{\frac{p-1}{2}}x^2 \equiv (-1)^{\frac{p+1}{2}}\pmod{p}.$$ Remark: I intend to use the relationship $g^{\frac{p-1}{2}} \...
2
votes
2answers
1k views

Expressing a Non Negative Integer as Sums of Two Squares

I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ...
2
votes
2answers
1k views

Highest power of 2

Highest power of two that divided $3^{1024}-1$ I did from binomial and expansion but is there a smarter way ? My approach : $ 3^{1024}-1 $ can be $(3^{512} + 1)$ and $(3^{512} – 1)$ Again$ ( 3^{...
2
votes
1answer
80 views

Estimation of a polynomial

I'm currently reading the following paper: http://arxiv.org/abs/1209.0612 and got stuck on Proposition 3.1 (2). The claim translated to polynomials is the following: Assume $n\geq 3, c\geq 1, d\...
2
votes
2answers
589 views

count digits up to number n

I am looking for the count of digits up to 1 million. Is there a formula for this? For example, the count of digits where $n = 10$ is $12$: $0 (+1)$ $1 (+1)$ $2 (+1)$ $3 (+1)$ $4 (+1)$ $5 (+1)$ $6 (...
2
votes
3answers
439 views

remainder problem based on 5 and 7

When a number is divided by 5 than remainder is 2 and when the same number is divided by 7 remainder is 4. What will be remainder be when the same number is divided by 35? What is the concept behind ...
2
votes
2answers
94 views

If $a + b \equiv 0 \pmod p$, and $a + b \equiv 0 \pmod q$, why does $a + b \equiv 0 \pmod {pq}$?

Put a bit more coherently, given $p$ and $q$ as distinct prime numbers, and thus $(p,q)=1$, if $$p^{(q-1)} + q^{(p-1)} \equiv 1 \pmod p$$ and $$p^{(q-1)} + q^{(p-1)} \equiv 1 \pmod q,$$ why does ...
2
votes
3answers
779 views

16 digit numbers divisible by 17

I wanted to know about the $16$ digit numbers those are divisible by $17$ and when this $16$ digit number is broken in groups of $4$ those groups of four are also divisible by $17$ and a check to ...
2
votes
1answer
125 views

Is there a pattern for reducing exponentiation to sigma sums?

The other day I was trying to find a method for cubing numbers similar to one I found for squaring numbers. I found that to find the square of a positive integer n, just sum up the first n odd ...
2
votes
3answers
852 views

Finding all integer solutions for $x^2 - 2y^2 =2 $

I'd love your help with finding all the integer solutions to the following equation: $x^2 - 2y^2 =2 $. I want to use Pell's theorem so I changed the equation to $-\frac{1}{2}x^2+ y^2 =-1$, Can I use ...
2
votes
5answers
107 views

How to show that $\mathrm{ord}_m a = \mathrm{ord}_m \overline{a}$?

Let $a \in Z$ and $m \in N$ such that $\gcd(a,m)=1$. How to show that $\mathrm{ord}_m a = \mathrm{ord}_m \overline{a}$, where $\overline{a}$ is the inverse of a modulo m? Hint: Solution starts as ...
2
votes
3answers
738 views

Prove that $(p-1)! \equiv (p-1) \pmod{1+2+3+\cdots+(p-1)}$

Given a prime number $p$ , establish the congruence: $$(p-1)! \equiv (p-1) \pmod{1+2+3+\cdots+(p-1)}$$ I have proceeded like this: $$\begin{align*}&(p-1)! \equiv (-1) \pmod{p} \quad \quad \...
2
votes
2answers
97 views

Unique solutions for $ab = n ^ 2$

How many unique solutions are there to the equation $ab = n^2$ , where $n$ is a constant, $a,b \geq 1$ and $a,b,n$ are integers. Is there any way of counting the number of solutions?
2
votes
2answers
895 views

Relatively prime numbers formula

Here is a problem I cannot manage with: Find two relatively prime positive numbers $p$, $q$ that satisfy: Sequence $ \{pn + q\}_{n=0,1,2,\ldots}$ does not contain any Fibonacci number. Any ...
2
votes
2answers
137 views

All Even-Numbered Convergents of a Finite Continued Fraction Are Less Than the Value

Let $x=[a_0;a_1,a_2]$ be shorthand notation for the continued fraction $$x=a_0+\frac{1}{a_1+\frac{1}{a_2}}.$$ Then every $x\in\mathbb{Q}$ can be represented as a finite continued fraction $[a_0;a_1,...
2
votes
4answers
86 views

$3^k$ not congruent to $-1 \pmod {2^e}, e > 2$.

$3^k \not\equiv -1 \pmod {2^e}$ for $e > 2, k > 0$. Is this true? I have tried to prove it by expanding $(1 + 2)^k$. [Notation: $(n; m) := n! / (m! (n - m)!)$] E.g., for $e = 3$ I get: $(1+2)^k +...
2
votes
3answers
326 views

Proof by contrapositive

Prove that if the product $ab$ is irrational, then either $a$ or $b$ (or both) must be irrational. How do I prove this by contrapositive? What is contrapositive?
2
votes
1answer
318 views

Complex Roots of Unity and the GCD

I'm looking for a proof of this statement. I just don't know how to approach it. I recognize that $z$ has $a$ and $b$ roots of unity, but I can't seem to figure out what that tells me. If $z \in \...
2
votes
2answers
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 ...
2
votes
2answers
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$ ...
2
votes
2answers
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-...
2
votes
1answer
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?
2
votes
2answers
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. ...
2
votes
1answer
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 ...
2
votes
1answer
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?
2
votes
1answer
560 views

Properties of the greatest common divisor and least common multiple

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])$.
2
votes
3answers
195 views

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 ...