I know the answer is x=k(n) where k is any whole number and n=29 But I have to prove this with the euclidean algorithm. I came to my answer by basic deduction.
How can I prove this with an euclidean algorithm (do not use an extended euclidean algorithm, that was made very clear by my teacher)
I cannot use gcd, I must use the euclidean algorithm to solve this and I need to show my work. I did end up with a 9 in my original solution but it's in the wrong spot.
Find x
ax==b mod n
13x==1 mod 29
d=gcd(a, n)
d=gcd(13, 29)
29 13 2 3
13 3 4 1::: use this row up in d=ns+ar
3 1 3 0
n a q gcd
d=1
d|b
1÷1=1 .... There are d roots, there is 1 root
d=n(s)+a(r)::: s1=1; r1=-q1; si=r(i-1); ri=s(i-1)-q(i)*r(i-1)
1=29s+13r //i just noticed a mistake I made here. For q1 I used -2 instead of -4 .... I will correct it in the answer I post
n s a r
13 1 3 -4
29 -4 13 9
x0=r(b)/d mod(n/d)
9(1)/1 mod(29/1)
x0=9
xi=x0+k(n/d)| k E Z
x1=9+1(29/1)=38
So I figure there's something wrong with the equation my idiotic teacher gave me. And maybe x0 should be my x1. Anyways, please point out any more mistakes than the ones I've already found like when she said use q1::2 instead of q(last-1)::4
And if this is EEA instead of EA please let me know. She made it very clear we MUST use EA and nothing else to solve this or we fail.
To find the solution practically, you do the extended Euclidean algorithm to $13$ and $29$ to find $x,y\in \Bbb Z$ such that $$13x + 29y = 1$$ and then the $x$ we found is as required, because if we reduce the equation modulo $29$ the second term becomes $0$ so that
$$13x \equiv 1 \pmod{29}$$
and so we have a solution $x$ (and all equivalent integers $x + 29k, k \in \Bbb Z$ also work).
For sure, $x=29k$ won't work, because that means $x \equiv 0 \pmod{29}$ and so also $13x \equiv 0 \pmod{29}$ and not $1$.
To see that some solution exists consider the numbers $13,26,39, \ldots \bmod{29}$, so $13,26,10,23,7,\ldots$ and then show (as we only have $29$ values) that this will repeat and that $1$ occurs among the values if $\gcd(13,29)=1$. The Euclidean algorithm as such doesn't have much to do with it. The greatest common divisor has, though.